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.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
Author information
Authors and Affiliations
Additional information
Received July 25, 1994; revised March 5, 1996.
Rights and permissions
About this article
Cite this article
Aggarwal, A., Kravets, D., Park, J. et al. Parallel Searching in Generalized Monge Arrays. Algorithmica 19, 291–317 (1997). https://doi.org/10.1007/PL00009175
Issue Date:
DOI: https://doi.org/10.1007/PL00009175