On the Average-Case Complexity of Selecting the kth Best

DOI10.1137/0211034MaRDI QIDQ3947142zbMATH OpenOpenAlexFDO

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)