2015/02/16 by Michał Karpiński, Karpiński, Michał, Marek Piotrów +1
Computer Science · #Advanced Algebra and Logic #Constraint Satisfaction and Optimization #Data Structures and Algorithms (cs.DS) #Distributed #FOS: Computer and information sciences #Logic, Reasoning, and Knowledge #Parallel #and Cluster Computing (cs.DC) #cs.DC #cs.DS
paper · pdf · doi:10.48550/arxiv.1502.04551
Extended version of the paper sent to CP2015
arxiv created 2015/02/16 · openalex publication_date 2015/02/16 · arxiv updated 2015/02/17 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Selection comparator networks have been studied for many years. Recently, they have been successfully applied to encode cardinality constraints for SAT-solvers. To decrease the size of generated formula there is a need for constructions of selection networks that can be efficiently generated and produce networks of small sizes for the practical range of their two parameters: n - the number of inputs (boolean variables) and k - the number of selected items (a cardinality bound). In this paper we give and analyze a new construction of smaller selection networks that are based on the pairwise selection networks introduced by Codish and Zanon-Ivry. We prove also that standard encodings of cardinality constraints with selection networks preserve arc-consistency.