Paper Info
Title
Perfect hashing and CNF encodings of cardinality constraints
Abstract
We study the problem of encoding cardinality constraints (threshold functions) on Boolean variables into CNF. Specifically, we propose new encodings based on (perfect) hashing that are efficient in terms of the number of clauses, auxiliary variables, and propagation strength. We compare the properties of our encodings to known ones, and provide experimental results evaluating their practical effectiveness.
Year
DOI
Venue
2012
10.1007/978-3-642-31612-8_30
SAT
Keywords
Field
DocType
propagation strength,practical effectiveness,boolean variable,cnf encodings,new encodings,auxiliary variable,cardinality constraint,threshold function
Discrete mathematics,Combinatorics,Computer science,Cardinality,Auxiliary variables,Conjunctive normal form,Perfect hash function,Hash function,Boolean data type,Encoding (memory)
Conference
Citations 
PageRank 
References 
8
0.51
9
Authors
4
Name
Order
Citations
PageRank
Y. Ben-Haim11408.29
Alexander Ivrii2827.97
Oded Margalit322818.85
Arie Matsliah424924.98