Content deleted Content added
join-tree clustering |
→Tree decomposition: solving algorithm |
||
Line 93:
The maximal number of variables of the cover used by a tree decomposition is a measure of the efficiency of solving the translated problem. The minimal such measure over all possible tree decompositions of a problem is a parameter called the ''treewidth'' of that problem.
===Solving from a tree decomposition===
A constraint satisfaction problem can be solved using one of its tree decomposition. An algorithm doing this proceeds creating constraints that are passed along the edges of the tree, from the leaves to the root and back.
These constraint represent the "interface" of a node towards another node. The rationale is that two nodes associated to variables <math>X_i</math> and <math>X_j</math> represent two constraints sharing variables <math>X_i \cap X_j</math>. The set of tuples over <math>X_i \cap X_j</math> that can be extended to <math>X_i</math> in such a way the first constraint is satisfied can be seen as a "summary" of how the constraint affects the shared variables.
The algorithm proceeds from the leaves of the tree. In each node, the summaries of its children (if any) are collected. These summary and the constraint of the node are used to generate the summary of the node for its parent. When the root is reached, the process is inverted: the summary of each node for each child is generated and sent it. When all leaves are reached, the algorithm stops.
===Reformulation===
Join-tree clustering is a particular form of tree decomposition in which:
Line 98 ⟶ 108:
* 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.
==See also==
| |||