World Scientific
  • Search
Skip main navigation

Cookies Notification

We use cookies on this site to enhance your user experience. By continuing to browse the site, you consent to the use of our cookies. Learn More
×
Our website is made possible by displaying certain online content using javascript.
In order to view the full content, please disable your ad blocker or whitelist our website www.worldscientific.com.

System Upgrade on Tue, Oct 25th, 2022 at 2am (EDT)

Existing users will be able to log into the site and access content. However, E-commerce and registration of new users may not be available for up to 12 hours.
For online purchase, please visit us again. Contact us at [email protected] for any enquiries.

All Nearest Smallers Made Simple

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

    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). CrossrefGoogle 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, ISIGoogle Scholar
    • 3. L. G. Valiant, Parallelism in comparison problems, SIAM J. Comput. 4 (1975) 348–355. CrossrefGoogle 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, ISIGoogle 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, ISIGoogle 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, ISIGoogle Scholar