Header menu link for other important links
Parallel searching in generalized Monge arrays
A. Aggarwal, D. Kravets, J.K. Park,
Published in Springer New York
Volume: 19
Issue: 3
Pages: 291 - 317
This paper investigates the parallel time and processor complexities of several searching problems involving Monge, staircase-Monge, and Monge-composite arrays. We present array-searching algorithms for concurrent-read-exclusive-write (CREW) PRAMs, hypercubes, and several hypercubic networks. All these algorithms run in near-optimal time, and their processor-time products are all within an O(lgn) factor of the worst-case sequential bounds. Several applications of these algorithms are also given. Two applications improve previous results substantially, and the others provide novel parallel algorithms for problems not previously considered. © 1997 Springer-Verlag New York Inc.
About the journal
Published in Springer New York
Open Access
Impact factor