An optimally efficient selection algorithm

DOI10.1016/0020-0190(88)90186-XzbMath0654.68069OpenAlexW2005608544MaRDI QIDQ1108805

Richard John Cole

Publication date: 1988

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(88)90186-x

zbMATH Keywords

selectionparallel algorithmEREW PRAMCRCW PRAM

Mathematics Subject Classification ID

Related Items (18)

Finding the k shortest paths in parallel ⋮ Improved upper bounds for time-space tradeoffs for selection with limited storage ⋮ Optimal Parallel Algorithms For Multiselection On Mesh-Connected Computers ⋮ An optimal parallel algorithm to construct a deap ⋮ Optimal, output-sensitive algorithms for constructing planar hulls in parallel ⋮ Fast deterministic selection on mesh-connected processor arrays ⋮ Finding an approximate median with high probability in constant parallel time ⋮ An optimal parallel algorithm for linear programming in the plane ⋮ Optimal parallel selection in sorted matrices ⋮ Two-variable linear programming in parallel ⋮ Two-variable linear programming in parallel ⋮ Efficient parallel algorithms for r-dominating set and p-center problems on trees ⋮ Approximate parallel scheduling. II: Applications to logarithmic-time optimal parallel graph algorithms ⋮ Improved fast integer sorting in linear space ⋮ Optimal parallel construction of heaps ⋮ On parallel integer sorting ⋮ Improving the efficiency of parallel minimum spanning tree algorithms ⋮ Selecting small ranks in EREW PRAM

Cites Work

• A parallel median algorithm
• Faster optimal parallel prefix sums and list ranking
• Deterministic coin tossing with applications to optimal parallel list ranking
• Parallelism in Comparison Problems
• The Parallel Evaluation of General Arithmetic Expressions

This page was built for publication: An optimally efficient selection algorithm