Content deleted Content added
→Solving from a tree decomposition: example with images |
→Reformulation: how bucket elimination is reformulated |
||
Line 134:
* 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 preceeds <math>x_i</math> in the ordering.
==See also==
| |||