All Nearest Smallers Made Simple
Abstract
In this paper, a parallel algorithm for all nearest smallers problem without using doubly logarithmic tree is described. It is shown that using only time routines for merging and prefix minima, we can easily get an time parallel algorithm for the all Nearest Smallers problem.
References
- 1. ,
Triangulating a monotone polygon in parallel , in Computational Geometry and Its Applications (CG 1988), ed. H. Noltemeier,Lecture Notes in Computer Science , Vol. 333 (Springer, Berlin, Heidelberg, 1988). Crossref, Google Scholar - 2. , Some Doubly logarithmic optimal parallel algorithms based on finding nearest smallers, J. Algorithms 14(3) (1993) 344–370. Crossref, ISI, Google Scholar
- 3. , Parallelism in comparison problems, SIAM J. Comput. 4 (1975) 348–355. Crossref, Google Scholar
- 4. , Introduction to Parallel Algorithms, 1st edition (Addison-Wesley Professional, 1992). Google Scholar
- 5. , Triply-logarithmic parallel upper and lower bounds for minimum and range minima over small domains, Journal of Algorithms 28(2) (August 1998) 197–215. Crossref, ISI, Google Scholar
- 6. , Finding the maximum, merging, and sorting in a parallel computation model, J. Algorithms 2(1) (1981) 88–102. Crossref, ISI, Google Scholar
- 7. , Routing, merging, and sorting on parallel models of computation, Journal of Computer and System Sciences 30(1) (February 1985) 130–145. Crossref, ISI, Google Scholar


