Lower Bounds on Merging Networks

DOI10.1145/321958.321976zbMath0335.68034OpenAlexW2078284127WikidataQ129275921 ScholiaQ129275921MaRDI QIDQ4102737

Andrew Chi-Chih Yao, F. Frances Yao

Publication date: 1976

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

Full work available at URL: http://hdl.handle.net/2027/uiuo.ark:/13960/t0wq1cx23

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Algorithms in computer science (68W99)

Related Items (11)

Bounds on the size of merging networks ⋮ A parallel sorting scheme whose basic operation sortsN elements ⋮ A gap between the actual complexity of permutations and their entropy defined by Stoss ⋮ Some minimum merging networks ⋮ Comparator networks for binary heap construction ⋮ Fragile complexity of adaptive algorithms ⋮ Fragile complexity of comparison-based algorithms ⋮ Fragile complexity of adaptive algorithms ⋮ Comparator networks for binary heap construction ⋮ A new parallel sorting algorithm based upon min-mid-max operations ⋮ Lower bounds for merging networks

This page was built for publication: Lower Bounds on Merging Networks