2005 · 40 citations · 4 references
ComputingComputer ScienceAlgorithmsData StructuresKnowledge RepresentationConstraint AnalysisConstraint ProgrammingConstraint RepresentationConstraint SatisfactionConstraint SolvingArc ConsistencyConstraint Satisfaction SearchConstraintsTable Constraints
The GAC-Scheme has become a popular general pur-pose algorithm for solving n-ary constraints, although it may scan an exponential number of supporting tuples. In this paper, we develop a major improvement of this scheme. When searching for a support, our new algo-rithm is able to skip over a number of tuples exponen-tial in the arity of the constraint by exploiting knowl-edge about the current domains of the variables. We demonstrate the effectiveness of the method for large table constraints.
4
Refining the Basic Constraint Propagation Algorithm.
Christian Bessière, Jean-Charles Régin · 2001 · 158 citations