Constraint satisfaction dual problem: Difference between revisions

Revision as of 16:23, 30 June 2011

Revision as of 03:59, 7 October 2012

Line 60:

Not all constraint satisfaction problems have a join tree. However, problems can be modified to acquire a join tree. [[Join-tree clustering]] is a specific method to modify problems in such a way they acquire a joint tree. This is done by merging constraints, which typically increases the size of the problem; however, solving the resulting problem is easy, as it is for all problems that have a join tree.

[[Decomposition method (constraint satisfaction)|Decomposition method]]s generalize join-tree clustering by grouping variables in such a way the resulting problem has a join tree. Decomposition methods directly associate a tree with problems; the nodes of this tree are associated varibablesvariables and/or constraints of the original problem. By merging constraints based on this tree, one can produce a problem that has a join tree, and this join tree can be easily derived from the decomposition tree. Alternatively, one can build a binary acyclic problem directly from the decomposition tree.

==References==