A Unified Lower Bound for Selection and Set Partitioning Problems

DOI10.1145/322234.322245MaRDI QIDQ3902518zbMATH OpenOpenAlexFDO

Authors David Kirkpatrick

Publication date 1981

Published in Journal of the ACM (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/322234.322245

zbMATH Keywords

analysis of algorithmsHasse diagramcomparison treeadversary strategy

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Searching and sorting (68P10) Discrete mathematics in relation to computer science (68R99)

Cited in

(16)

• Progress in selection
• Selecting the k largest elements with parity tests
• Architecture independent parallel selection with applications to parallel priority queues
• Randomized selection in \(n+C+o(n)\) comparisons
• Closing a long-standing complexity gap for selection: \(V _{3}(42) = 50\)
• Selection Algorithms with Small Groups
• On partial sorting in restricted rounds
• Optimal Parallel Algorithms For Multiselection On Mesh-Connected Computers
• scientific article; zbMATH DE number 7765400 (Why is no real title available?)
• On computing an optimal permutation of ranks for multiselection
• Finding a mediocre player
• Select with groups of 3 or 4
• A note on upper bounds for the selection problem
• Errata to ``Selecting the top three elements by M. Aigner: A result of a computer-assisted proof search
• A selectable sloppy heap
• Optimal parallel selection in sorted matrices

This page was built for publication: A Unified Lower Bound for Selection and Set Partitioning Problems

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