Decomposition method (constraint satisfaction): Difference between revisions

Revision as of 00:19, 10 January 2019

Revision as of 23:44, 14 January 2019

Line 108:

===Hinge decomposition===

AnA hinge is a subset of nodes of hypergraph having some properties defined below. AnA 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 w.r.t. <math>H</math>.