Propagation in CSP and SAT
Date
2006ISSN
0302-9743Source
12th International Conference on Principles and Practice of Constraint Programming, CP 2006Volume
4204 LNCSPages
137-151Google Scholar check
Keyword(s):
Metadata
Show full item recordAbstract
Constraint Satisfaction Problems and Prepositional Satisfiability, are frameworks widely used to represent and solve combinatorial problems. A concept of primary importance in both frameworks is that of constraint propagation. In this paper we study and compare the amount of propagation that can be achieved, using various methods, when translating a problem from one framework into another. Our results complement, extend, and tie together recent similar studies. We provide insight as to which translation is preferable, with respect to the strength of propagation in the original problem and the encodings. © Springer-Verlag Berlin Heidelberg 2006.