Content deleted Content added
summarized clustering and decomposition that are already in decomposition method |
|||
Line 47:
A graph obtained from the dual graph by removing some redundant edges is called a ''join graph''. If it is a tree, it is called a ''join tree''. The dual problem can be solved from a join graph since all removed edges are redundant. In turn, the problem can be solved efficiently if that join graph is a tree, using algorithms tailored for acyclic constraint satisfaction problems.
Finding a join tree, if any, can be done exploiting the following property: if a dual graph has a join tree, then the maximal-weight [[spanning tree (mathematics)|spanning tree]]s of the graph are all join trees, if edges are weighted by the number of variables the corresponding constraints enforce to be equal. An algorithm for finding a join tree, if any, proceeds as follows. In the first step, edges are assigned weights: if two nodes represent constraints that share <math>n</math> variables, the edge joining them is assigned weight <math>n</math>. In the second step, a maximal-weight spanning tree is searched for. Once one is found, it is checked whether it enforces the required equality of variables. If this is the case, this spanning tree is a join tree.
Another method for finding out whether a constraint satisfaction problem has a join tree uses the primal graph of the problem, rather than the dual graph. The ''primal graph'' of a constraint satisfaction problem is a graph whose nodes are problem variables and whose edges represent the presence of two variables in the same constraint. A join tree for the problem exists if:
| |||