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

Omer Berkman, Baruch Schieber, Uzi Vishkin

Research output: Contribution to journalArticlepeer-review

77 Scopus citations

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.

Original languageEnglish (US)
Pages (from-to)344-370
Number of pages27
JournalJournal of Algorithms
Volume14
Issue number3
DOIs
StatePublished - May 1993
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Control and Optimization
  • Computational Mathematics
  • Computational Theory and Mathematics

Fingerprint

Dive into the research topics of 'Optimal doubly logarithmic parallel algorithms based on finding all nearest smaller values'. Together they form a unique fingerprint.

Cite this