Publication
Journal of Algorithms
Paper

Optimal doubly logarithmic parallel algorithms based on finding all nearest smaller values

View publication

Abstract

The all nearest smaller values problem is defined as follows. Let A = (a1, a2, an) be n elements drawn from a totally ordered domain. For each ai, 1 ≤ i ≤ n, find the two nearest elements in A that are smaller than ai (if such exist): the left nearest smaller element aj (with j < i) and the right nearest smaller element ak (with k > i). We give an O(log log n) time optimal parallel algorithm for the problem on a CRCW PRAM. We apply this algorithm to achieve optimal O(log log n) time parallel algorithms for four problems: (i) Triangulating a monotone polygon, (ii) Preprocessing for answering range minimum queries in constant time, (iii) Reconstructing a binary tree from its inorder and either preorder or postorder numberings, (vi) Matching a legal sequence of parentheses. We also show that any optimal CRCW PRAM algorithm for the triangulation problem requires Ω(log log n) time. © 1993 Academic Press, Inc.

Date

Publication

Journal of Algorithms

Authors

Share