On the Average-Case Complexity of Selecting the kth Best

DOI10.1137/0211034zbMATH Open0486.68069OpenAlexW2152904264MaRDI QIDQ3947142FDOQ3947142

Authors: Andrew Chi-Chih Yao, F. Frances Yao 

Publication date: 1982

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/4c0e0cbe9b40f98da6b5322d06f12e1ffcd81926

zbMATH Keywords

selectiondecision treebinary treeminimum average number of pairwise comparisons

Mathematics Subject Classification ID

Discrete mathematics in relation to computer science (68R99)

Cited In (5)

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

This page was built for publication: On the Average-Case Complexity of Selecting the kth Best

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