Parallel selection

DOI10.1016/0166-218X(90)90128-YzbMath0699.68085OpenAlexW2912298798MaRDI QIDQ913517

Yossi Azar, Nicholas J. Pippenger

Publication date: 1990

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0166-218x(90)90128-y

zbMATH Keywords

selectionworst caseparallel comparison tree

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Searching and sorting (68P10)

Related Items (6)

Transforming comparison model lower bounds to the parallel-random-access-machine ⋮ Heap construction in the parallel comparison tree model ⋮ Fast deterministic selection on mesh-connected processor arrays ⋮ Optimal parallel construction of heaps ⋮ Parallel comparison merging of many-ordered lists ⋮ Parallel comparison algorithms for approximation problems

Cites Work

• Unnamed Item
• Unnamed Item
• Sorting in \(c \log n\) parallel steps
• Time bounds for selection
• Searching, Merging, and Sorting in Parallel Computation
• Applying Parallel Computation Algorithms in the Design of Serial Algorithms
• Sorting and Selecting in Rounds
• Tight Comparison Bounds on the Complexity of Parallel Sorting
• Sorting, Approximate Sorting, and Searching in Rounds
• Finding an Approximate Maximum
• Sorting and Merging in Rounds
• Parallelism in Comparison Problems
• Slowing down sorting networks to obtain faster sorting algorithms
• On the theory of graphs

This page was built for publication: Parallel selection