Decomposition method (constraint satisfaction): Difference between revisions

Revision as of 13:31, 4 July 2008

Revision as of 13:11, 13 August 2008

Line 106:

===Hinge decomposition===

An hinge is a subset of nodes of hypergraph having having some properties defined below. An hinge decomposition is based on the sets of variables that are minimal hinges of the hypergraph whose nodes are the variables of the constraint satisfaction problem and whose hyperedges are the scopes of its constraints.

The definition of hinge is as follows. Let <math>H</math> be a set of hyperedges. A path w.r.t. <math>H</math> is a sequence of edges such that the intersection of each one with the next one is non-empty and not contained in the nodes of <math>H</math>. A set of edges is connected w.r.t. <math>H</math> if, for each pair of its edges, there is a path w.r.t. <math>H</math> of which the two nodes are the first and the last edge. A connected component w.r.t. <math>H</math> is a maximal set of connected edges.