A computer-assisted optimal depth lower bound for nine-input sorting networks

DOI10.1007/BF02090393zbMath0722.68031WikidataQ56337894 ScholiaQ56337894MaRDI QIDQ3210158

Ian Parberry

Publication date: 1991

Published in: Mathematical Systems Theory (Search for Journal in Brave)

zbMATH Keywords

parallel computinglower boundsorting network

Mathematics Subject Classification ID

Searching and sorting (68P10) Network design and communication in computer systems (68M10)

Related Items

Optimizing sorting algorithms by using sorting networks, Optimal-depth sorting networks, New Bounds on Optimal Sorting Networks, Formalizing Size-Optimal Sorting Networks: Extracting a Certified Proof Checker, Sorting networks: to the end and back again, Formally proving size optimality of sorting networks, Sorting nine inputs requires twenty-five comparisons, Applying Sorting Networks to Synthesize Optimized Sorting Libraries, Single-exception sorting networks and the computational complexity of optimal sorting network verification

Cites Work

• Sorting in \(c \log n\) parallel steps
• On the time required to sum n semigroup elements on a parallel machine with simultaneous writes
• A Sorting Problem
• Single-exception sorting networks and the computational complexity of optimal sorting network verification
• Efficient generation of the binary reflected gray code and its applications
• An Improved Lower Bound for Sorting Networks
• Unnamed Item
• Unnamed Item
• Unnamed Item