A Counting Approach to Lower Bounds for Selection Problems

DOI10.1145/322123.322128MaRDI QIDQ4181962zbMATH OpenOpenAlexFDO

Authors Frank Fussenegger, Harold N. Gabow

Publication date 1979

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

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

zbMATH Keywords

Chaos FunctionsComparison TreeComplexityLower BoundsSelection Problems

Mathematics Subject Classification ID

Information storage and retrieval of data (68P20) Analysis of algorithms and problem complexity (68Q25)

Cited in

(16)

• Bounds for min-max heaps
• On the distribution of comparisons in sorting algorithms
• On selecting the k largest with median tests
• On selecting the k largest with restricted quadratic queries
• The double selection problem
• Decision trees: Old and new results.
• Selecting the k largest elements with parity tests
• A selectable sloppy heap
• Selection problems via \(m\)-ary queries
• Select with groups of 3 or 4
• Selection Algorithms with Small Groups
• Progress in selection
• Finding a mediocre player
• scientific article; zbMATH DE number 7765400 (Why is no real title available?)
• Coping with known patterns of lies in a search game
• On the time-space tradeoff for sorting with linear queries

This page was built for publication: A Counting Approach to Lower Bounds for Selection Problems

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