Decomposition method (constraint satisfaction): Difference between revisions

Revision as of 17:41, 10 October 2008

Revision as of 19:50, 21 November 2008

Line 188:

===Generalized hypertree decomposition===

Generalized hypertree decompositions are defined like hypertree decompositions, but the last requirement is dropped; this is the condition "the variables of the constraints of a node that are not variables of the node do not occur in the subtree rooted at the node". A problem can be clearly solved in polynomial time if a fixed-width decomposition of it is given. However, the restriction to a fixed width is not known to being tractable, as the complexity of finding a decomposition of fixed width even if one is known to exist is not known, [[as{{As of |2001]]|lc=on}}.

==Comparison==