Constraint satisfaction dual problem: Difference between revisions

Revision as of 00:46, 5 March 2006

Revision as of 15:52, 19 March 2006

Line 85:

This translation requires the maximal cliques of a chordal graph to be identified. However, this can bone easily using the same ordering used for enforcing chordality. Since the parents of each node are all connected to each other, the maximal cliques are composed of a node (the maximal node of the clique in a max-cardinality ordering) and all its parents. As a result, these maximal cliques can be detected by considering each node with its parents.

The problem that results from this process has a join tree. A join tree can be obtained by using the same ordering of variables again. Proceeding from the last node to the first, every constraint is connected with the preceedingpreceding constraint that shares more variables with it.

==Tree decomposition==