Closing a long-standing complexity gap for selection: V _3(42) = 50

DOI10.1007/978-3-642-40273-9_6MaRDI QIDQ2848968zbMATH OpenOpenAlexFDO

Authors David Kirkpatrick

Publication date 13 September 2013

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-40273-9_6

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Recommendations

• The double selection problem
• Select with groups of 3 or 4
• On selecting the k largest with median tests
• Complexity of selection in \(X+Y\)
• scientific article; zbMATH DE number 4026821

Cites work

• scientific article; zbMATH DE number 3473265 (Why is no real title available?)
• scientific article; zbMATH DE number 3322504 (Why is no real title available?)
• scientific article; zbMATH DE number 3342853 (Why is no real title available?)
• A Unified Lower Bound for Selection and Set Partitioning Problems
• An efficient algorithm for partial order production
• Automata, Languages and Programming
• Average case selection
• Errata to ``Selecting the top three elements by M. Aigner: A result of a computer-assisted proof search
• Optimal Time Minimal Space Selection Algorithms
• Selecting the top three elements
• Selection and sorting with limited storage

Cited in

(4)

• Selection Algorithms with Small Groups
• On partial sorting in restricted rounds
• Select with groups of 3 or 4
• A selectable sloppy heap

This page was built for publication: Closing a long-standing complexity gap for selection: \(V _{3}(42) = 50\)

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