Sorting networks: the end game

DOI10.1007/978-3-319-15579-1_52MaRDI QIDQ2799216zbMATH OpenOpenAlexFDO

Authors Michael Codish, Luís Cruz-Filipe, Peter Schneider-Kamp

Publication date 8 April 2016

Published in Language and Automata Theory and Applications (Search for Journal in Brave)

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

zbMATH Keywords

SAT-solvingsorting networkssymmetry breaking

Mathematics Subject Classification ID

Searching and sorting (68P10) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Abstract: This paper studies properties of the back end of a sorting network and illustrates the utility of these in the search for networks of optimal size or depth. All previous works focus on properties of the front end of networks and on how to apply these to break symmetries in the search. The new properties help shed understanding on how sorting networks sort and speed-up solvers for both optimal size and depth by an order of magnitude.

Recommendations

• Sorting networks: to the end and back again
• Optimal sorting networks
• Optimal-depth sorting networks
• New Bounds on Optimal Sorting Networks
• Improved sorting networks with O(log N) depth

Cited in

(9)

• An improved subsumption testing algorithm for the optimal-size sorting network problem
• Sorting networks: to the end and back again
• Optimizing sorting algorithms by using sorting networks
• New Bounds on Optimal Sorting Networks
• A Robust Sorting Network
• Optimal-depth sorting networks
• Merging almost sorted sequences yields a 24-sorter
• On the analysis of sorting networks from the viewpoint of circuit theory
• Applying sorting networks to synthesize optimized sorting libraries

This page was built for publication: Sorting networks: the end game

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