Skip to main content
Log in

Parallel Searching in Generalized Monge Arrays

  • Published:
Algorithmica Aims and scope Submit manuscript

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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

Author information

Authors and Affiliations

Authors

Additional information

Received July 25, 1994; revised March 5, 1996.

Rights and permissions

Reprints 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

Download citation

  • Issue Date:

  • DOI: https://doi.org/10.1007/PL00009175

Navigation