An optimally efficient selection algorithm

DOI10.1016/0020-0190(88)90186-XMaRDI QIDQ1108805zbMATH OpenOpenAlexFDO

Authors Richard 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

parallel algorithmselectionEREW PRAMCRCW PRAM

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 2079315
• Optimal parallel selection
• Optimal parallel multiselection on EREW PRAM
• scientific article; zbMATH DE number 4082988
• An optimal parallel algorithm for the multiselection problem

Cites work

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

Cited in

(33)

• Finding an approximate median with high probability in constant parallel time
• Two-variable linear programming in parallel
• On parallel integer sorting
• Efficient selection on a binary tree
• Selecting small ranks in EREW PRAM
• Efficient parallel algorithms for r-dominating set and p-center problems on trees
• Improved fast integer sorting in linear space
• Coarse grained parallel selection
• Fast deterministic selection on mesh-connected processor arrays
• Selection Algorithms with Small Groups
• Finding the \(k\) shortest paths in parallel
• Improving the efficiency of parallel minimum spanning tree algorithms
• Query-based selection of optimal candidates under the Mallows model
• Approximate parallel scheduling. II: Applications to logarithmic-time optimal parallel graph algorithms
• Optimal Parallel Algorithms For Multiselection On Mesh-Connected Computers
• Fast Deterministic Selection
• Optimal, output-sensitive algorithms for constructing planar hulls in parallel
• scientific article; zbMATH DE number 3894470 (Why is no real title available?)
• Optimal parallel construction of heaps
• An optimal parallel algorithm for linear programming in the plane
• scientific article; zbMATH DE number 4163827 (Why is no real title available?)
• Efficient algorithms for approximate smooth selection
• Fundamentals of Computation Theory
• An optimal parallel algorithm to construct a deap
• Energy efficient sorting, selection and searching
• scientific article; zbMATH DE number 2079315 (Why is no real title available?)
• Two-variable linear programming in parallel
• An optimal parallel algorithm for the multiselection problem
• Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems
• Using ordinal optimization approach to improve efficiency of selection procedures
• Optimal parallel selection in sorted matrices
• Improved upper bounds for time-space tradeoffs for selection with limited storage
• scientific article; zbMATH DE number 3980537 (Why is no real title available?)

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1108805)