Content deleted Content added
→Join-tree clustering: example with images |
→Solving from a tree decomposition: example with images |
||
Line 112:
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.
{| cellpadding=10 style="border: gray thin solid;"
|-
| [[Image:Solving-tree-decomposition-1.svg]]
| [[Image:Solving-tree-decomposition-2.svg]]
| [[Image:Solving-tree-decomposition-3.svg]]
| [[Image:Solving-tree-decomposition-4.svg]]
|-
| A tree decomposition with associated constraints. All variables have ___domain {0,..,10} in this example.
| The leftmost node contains the constraint a<b and shares the variable b with its parent. These constraint allow b only to take values greater than or equal to 1. This constraint b>0 is sent to its parent.
| The left child of the root receives the constraint b>0 and combines it with its constraint b<c. It shares c with its parent, and the two constraints enforce c>1. This constraint is sent to its parent.
| When the root has received constraints for all its children, it combines them and sends constraints back to them. The process ends when all leaves are reached. At this point, the allowed values of variables are explicit.
|}
===Reformulation===
| |||