Constraint satisfaction dual problem: Difference between revisions

Revision as of 12:30, 26 April 2006

Revision as of 12:53, 26 April 2006

Line 141:

===Reformulation===

[[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 precedes <math>x_i</math> in the ordering.

Join-tree clustering is a particular form of tree decomposition in which:

* the elements of the cover are the cliques of the graph resulting from enforcing chordality;

* the tree is the join tree;

* 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 precedes <math>x_i</math> in the ordering.

==See also==