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

DOI10.1007/978-3-642-40273-9_6zbMATH Open1394.68185OpenAlexW30731058MaRDI QIDQ2848968FDOQ2848968

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

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

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Cites Work

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

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)