Content deleted Content added
other decompositions |
m demoted sections |
||
Line 163:
The definition of tree decomposition given above can be used for non-binary constraint satisfaction problems, but was initially defined for binary problems only. The translations defined specifically for non-binary constraints are the query decomposition and the hyper-tree decomposition. These translation specify how constraints are mapped into the nodes of the tree.
===Query decomposition===
A query decomposition of a constraint satisfaction problem is based on associating sets of constraints and variables to each node of a tree. This is similar to a tree decomposition, but the association of constraints to nodes of the tree is made explicit. In addition, it is assumed that the subtree of nodes associated to a given constraint is connected, while this assumption is not present in tree decompositions.
===Hypertree decomposition===
A complete hypertree decomposition allows constraints to be associated to some nodes that do not contains all of their variables. This association is however constrained as follows:
| |||