Parallel selection

DOI10.1016/0166-218X(90)90128-YMaRDI QIDQ913517zbMATH OpenOpenAlexFDO

Authors Yossi Azar, Nicholas 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)

Recommendations

• A time-randomness tradeoff for selection in parallel
• Probabilistic Parallel Algorithms for Sorting and Selection
• Publication:3359742
• Publication:4471267
• Optimal parallel selection

Cites work

• scientific article; zbMATH DE number 3735871 (Why is no real title available?)
• scientific article; zbMATH DE number 1142304 (Why is no real title available?)
• Applying Parallel Computation Algorithms in the Design of Serial Algorithms
• Finding an Approximate Maximum
• On the theory of graphs
• Parallelism in Comparison Problems
• Searching, Merging, and Sorting in Parallel Computation
• Slowing down sorting networks to obtain faster sorting algorithms
• Sorting and Merging in Rounds
• Sorting and Selecting in Rounds
• Sorting in \(c \log n\) parallel steps
• Sorting, Approximate Sorting, and Searching in Rounds
• Tight Comparison Bounds on the Complexity of Parallel Sorting
• Time bounds for selection

Cited in

(13)

• An improved, randomized algorithm for parallel selection with an experimental study
• Finding an approximate median with high probability in constant parallel time
• Optimal parallel selection
• Transforming comparison model lower bounds to the parallel-random-access-machine
• Heap construction in the parallel comparison tree model
• Optimal parallel construction of heaps
• A time-randomness tradeoff for selection in parallel
• Fast deterministic selection on mesh-connected processor arrays
• Parallel comparison merging of many-ordered lists
• Asynchronous exclusive selection
• A parallel selection algorithm
• Parallel comparison algorithms for approximation problems
• Parallel Selection with High Probability

This page was built for publication: Parallel selection

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