Constraint satisfaction dual problem: Difference between revisions

Revision as of 13:41, 25 February 2006

Revision as of 13:44, 25 February 2006

Line 109:

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.

[[Image:Passing-constraint.svg|thumb|220px|The constraint passed from node i to node j tellssummarizes howthe effects of the nodes on the "side" of i affectto the variables of j.]]

In a tree, every edge breaks the graph in two parts. The constraint passed along an edge tells how the part of the originating end of the edge affects the variables of the destination node. In other words, a constraint passed from node <math>i</math> to node <math>j</math> tells how the nodes "on the side of <math>i</math>" constrain the variables of node <math>j</math>.