Decomposition method (constraint satisfaction): Difference between revisions

Revision as of 19:44, 4 November 2007

Revision as of 03:38, 5 December 2007

Line 188:

===Generalized hypertree decomposition===

Generalized hypertree decompositions are defined linklike hypertree decompositiondecompositions, 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 of 2001]].

==Comparison==