Constraint satisfaction dual problem: Difference between revisions

Revision as of 21:07, 12 April 2006

Revision as of 21:07, 12 April 2006

Line 54:

# the variables of every maximal clique of the primal graph are the scope of a constraint and vice versa; this property is called ''conformality''.

In turn, chordality can be checked using a [[max-cardinality ordering]] of the variables. Such an ordering can also be used, if the two conditions above are met, for finding a join tree of the problem. Ordering constraints by their highest variable according to the ordering, an algorithm for producing a join tree proceeds from the last to the first constraint; at each step, a constraint is connected to the constraint that shares a maximal number of variables with it among the constraints that preceedprecede it in the ordering.

==Join-tree clustering==