A Counting Approach to Lower Bounds for Selection Problems
From MaRDI portal
Publication:4181962
DOI10.1145/322123.322128zbMath0398.68018OpenAlexW2151407355MaRDI QIDQ4181962
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
Analysis of algorithms and problem complexity (68Q25) Information storage and retrieval of data (68P20)
Related Items (16)
Selection problems via \(m\)-ary queries ⋮ Select with Groups of 3 or 4 ⋮ Progress in selection ⋮ Bounds for min-max heaps ⋮ On the distribution of comparisons in sorting algorithms ⋮ On selecting the k largest with median tests ⋮ Unnamed Item ⋮ On selecting the \(k\) largest with restricted quadratic queries ⋮ Selecting the \(k\) largest elements with parity tests ⋮ The double selection problem ⋮ Finding a mediocre player ⋮ A selectable sloppy heap ⋮ Selection Algorithms with Small Groups ⋮ Coping with known patterns of lies in a search game ⋮ Decision trees: Old and new results. ⋮ 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
