Optimal-depth sorting networks

DOI10.1016/j.jcss.2016.09.004zbMath1353.68062arXiv1412.5302OpenAlexW1726079515MaRDI QIDQ340576

Michael Codish, Jakub Závodný, Luís Cruz-Filipe, Peter Schneider-Kamp, Daniel Bundala

Publication date: 14 November 2016

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1412.5302

zbMATH Keywords

symmetry breakingSAT solvingsorting networks

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Searching and sorting (68P10)

Related Items (3)

The Half Cleaner Lemma: Constructing Efficient Interconnection Networks from Sorting Networks ⋮ Sorting networks: to the end and back again ⋮ Practical Algorithms for Finding Extremal Sets

Uses Software

• nauty
• Traces
• BEE

Cites Work

• Unnamed Item
• Unnamed Item
• Computer-aided proof of Erdős discrepancy properties
• Sorting nine inputs requires twenty-five comparisons
• Bounds on the size of test sets for sorting and related networks
• Isomorphism of graphs of bounded valence can be tested in polynomial time
• Every planar map is four colorable. I: Discharging
• Every planar map is four colorable. II: Reducibility
• Computing the Ramsey number \(R(4,3,3)\) using abstraction and symmetry breaking
• Sorting networks: to the end and back again
• Practical graph isomorphism. II.
• Sorting Networks: The End Game
• Solving and Verifying the Boolean Pythagorean Triples Problem via Cube-and-Conquer
• New Bounds on Optimal Sorting Networks
• A computer-assisted optimal depth lower bound for nine-input sorting networks
• Compiling finite domain constraints to SAT withBEE
• Boolean Equi-propagation for Concise and Efficient SAT Encodings of Combinatorial Problems
• Optimal Sorting Networks
• Applying Sorting Networks to Synthesize Optimized Sorting Libraries

This page was built for publication: Optimal-depth sorting networks