Optimal parallel selection has complexity O(log log N)

DOI10.1016/0022-0000(89)90035-4zbMath0668.68044OpenAlexW2072783164MaRDI QIDQ1118404

János Komlós, Endre Szemerédi, Miklós Ajtai, William Steiger

Publication date: 1989

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0022-0000(89)90035-4

zbMATH Keywords

sortingparallel computationparallel complexitysearchexpander graphs

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Searching and sorting (68P10) Extremal problems in graph theory (05C35) Graph theory (including graph drawing) in computer science (68R10)

Related Items

Transforming comparison model lower bounds to the parallel-random-access-machine, Select with Groups of 3 or 4, Recursive construction for 3-regular expanders, Heap construction in the parallel comparison tree model, Fast deterministic selection on mesh-connected processor arrays, A complexity theory of efficient parallel algorithms, Unnamed Item, A selectable sloppy heap, Selection Algorithms with Small Groups

Cites Work

• Unnamed Item
• Sorting in \(c \log n\) parallel steps
• A parallel median algorithm
• Routing, merging, and sorting on parallel models of computation
• Explicit constructions of linear-sized superconcentrators
• Time bounds for selection
• Parallelism in Comparison Problems