2015/02/20 by Martin Marinov, Marinov, Martin, David Gregg +1
Computer Science · #Complexity and Algorithms in Graphs #Data Mining Algorithms and Applications #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #F.2.2 #FOS: Computer and information sciences #Graph Theory and Algorithms
paper · pdf · doi:10.48550/arxiv.1502.05983
openalex publication_date 2015/02/20 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In this paper we extend the knowledge on the problem of empirically searching for sorting networks of minimal depth. We present new search space pruning techniques for the last four levels of a candidate sorting network by considering only the output set representation of a network. We present an algorithm for checking whether an n-input sorting network of depth d exists by considering the minimal up to permutation and reflection itemsets at each level and using the pruning at the last four levels. We experimentally evaluated this algorithm to find the optimal depth sorting networks for all n ≤ 12.