A filtering process for general constraint-satisfaction problems: achieving pairwise-consistency using an associated binary representation
Pierre Janssen, Philippe Jégou, B. NOUGUIER, Marie-Catherine Vilarem · 2003
Considers the use of a partial consistency, issuing from relational database theory, within the constraint-satisfaction problems (CSPs) framework, i.e., pairwise consistency. This partial consistency concerns general CSPs (i.e., CSPs the constraints of which may involve more than two variables). The authors provide a polynomial algorithm for achieving this consistency; then they extend the class of polynomially solvable CSPs. This algorithm is based on a minimal binary representation of a general CSP.>