Lower Bounds on Merging Networks

DOI10.1145/321958.321976MaRDI QIDQ4102737zbMATH OpenOpenAlexWikidataFDO

Authors 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)

Cited in

(12)

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

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

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