Decomposition method (constraint satisfaction): Difference between revisions

Revision as of 20:31, 4 May 2008

Revision as of 20:31, 4 May 2008

Line 165:

|-

| A hypergraph representation of a constraint satisfaction problem: the constraints are given names (P, Q, R, S, T), and their scopes are shown (P (a, b, c) means that constraint P is on the variables {a, b, c}

| A query decomposition of the problem. Nodes may contain variables, constraints, or both. Although to the rightmost node areis associated a total of fivesix variables (i.e. a,b,c,d,e among the two constraints), this is a decomposition of width 3 because no node contains more then three between constraints and isolated variables (there is another decomposition of width 2 and it is possible to show that this decomposition og width 2 is the minimum width of this hypergraph).

|}