ISSN:
1432-0541
Keywords:
Key words. Monge arrays, CREW-PRAM algorithms, Hypercubes.
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
,
Mathematics
Notes:
Abstract. 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 (\lg n)$ 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.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/PL00009175
