Randomized range-maxima in nearly-constant parallel time

DOI10.1007/BF01200429zbMath0770.68060MaRDI QIDQ1210333

Omer Berkman, Yossi Matias, Uzi Vishkin

Publication date: 16 September 1993

Published in: Computational Complexity (Search for Journal in Brave)

zbMATH Keywords

randomized algorithmCRCW PRAMparallel comparison modelprefix maximumrange-maxima

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Distributed algorithms (68W15)

Related Items (3)

Parallel algorithms for connectivity problems on interval graphs ⋮ The complexity of parallel prefix problems on small domains ⋮ Prefix graphs and their applications

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The average-case parallel complexity of sorting
• Routing, merging, and sorting on parallel models of computation
• Nonlinearity of Davenport-Schinzel sequences and of generalized path compression schemes
• Fast probabilistic algorithms for Hamiltonian circuits and matchings
• Fast Algorithms for Finding Nearest Common Ancestors
• Probabilistic Parallel Algorithms for Sorting and Selection
• Tight Comparison Bounds on the Complexity of Parallel Sorting
• The Average Complexity of Deterministic and Randomized Parallel Comparison-Sorting Algorithms
• Finding the maximum, merging, and sorting in a parallel computation model
• Efficiency of a Good But Not Linear Set Union Algorithm
• Parallelism in Comparison Problems
• Optimal Doubly Logarithmic Parallel Algorithms Based On Finding All Nearest Smaller Values
• A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations

This page was built for publication: Randomized range-maxima in nearly-constant parallel time