Constraint satisfaction dual problem: Difference between revisions

Revision as of 19:49, 10 April 2006

Revision as of 21:07, 12 April 2006

Line 157:

* every constraint is assigned to all nodes of the tree whose sets of variables contain the scope of the constraint.

[[Bucket elimination]] can also be reformulated as an algorithm working on a particular tree decomposition. In particular, given an ordering of the variables, every variable is associated a bucket containing all constraints such that the variable is the greatest in their scope. Bucket elimination corresponds to the tree decomposition that has a node for each bucket. This node is associated all of its constraints, and corresponds to the set of all variables of these constraints. The parent of a node associated to the bucket of <math>x_i</math> is the node associated to the bucket of <math>x_j</math>, where <math>x_j</math> is the greatest node that is in a constraint with <math>x_i</math> and preceedsprecedes <math>x_i</math> in the ordering.

==Non-binary tree decompositions==