No Access

All Nearest Smallers Made Simple

Dept. of Computer Science and Engineering, Indian Institute of Technology, Kanpur 208 016, India

https://doi.org/10.1142/S0129626420500085Cited by:0 (Source: Crossref)

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 $O (log log n)$ time routines for merging and prefix minima, we can easily get an $O (log log n)$ time parallel algorithm for the all Nearest Smallers problem.

Keywords:

References

1. H. Wagener, 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. O. Berkman, B. Schieber and U. Vishkin, Some Doubly logarithmic optimal parallel algorithms based on finding nearest smallers, J. Algorithms 14(3) (1993) 344–370. Crossref, Web of Science, Google Scholar
3. L. G. Valiant, Parallelism in comparison problems, SIAM J. Comput. 4 (1975) 348–355. Crossref, Google Scholar
4. J. JaJa, Introduction to Parallel Algorithms, 1st edition (Addison-Wesley Professional, 1992). Google Scholar
5. O. Berkman, Y. Matias and P. Ragde, 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, Web of Science, Google Scholar
6. Y. Shiloach and U. Vishkin, Finding the maximum, merging, and sorting in a parallel computation model, J. Algorithms 2(1) (1981) 88–102. Crossref, Web of Science, Google Scholar
7. A. Borodin and J. E. Hopcroft, Routing, merging, and sorting on parallel models of computation, Journal of Computer and System Sciences 30(1) (February 1985) 130–145. Crossref, Web of Science, Google Scholar