Triply-logarithmic upper and lower bounds for minimum, range minima, and related problems with integer inputs

DOI10.1007/3-540-57155-8_246zbMath1504.68280OpenAlexW1795349118MaRDI QIDQ5060111

Yossi Matias, Omer Berkman, Prabhakar Ragde

Publication date: 18 January 2023

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/3-540-57155-8_246

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Parallel algorithms in computer science (68W10)

Related Items

Transforming comparison model lower bounds to the parallel-random-access-machine ⋮ Almost fully-parallel parentheses matching ⋮ Parallel algorithms for connectivity problems on interval graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Simulations among concurrent-write PRAMs
• Searching, Merging, and Sorting in Parallel Computation
• Intersection Theorems for Systems of Sets
• Fast Algorithms for Finding Nearest Common Ancestors
• On Parallel Searching
• The Parallel Complexity of Element Distinctness is $\Omega ( \sqrt{\log n} )$
• On Finding Lowest Common Ancestors: Simplification and Parallelization
• Finding the maximum, merging, and sorting in a parallel computation model
• Parallelism in Comparison Problems
• Optimal Doubly Logarithmic Parallel Algorithms Based On Finding All Nearest Smaller Values
• Triangulating a polygon in parallel