Content deleted Content added
m →Cycle hypercutset: spelling fix |
|||
Line 110:
An hinge is a subset of nodes of hypergraph 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 w.r.t. <math>H</math>.
Hinges are defined for reduced hypergraphs, which are hypergraphs where no hyperedge is contained in another. A set of at least two edges <math>H</math> is a hinge if, for every connected component <math>F</math> w.r.t. <math>H</math>, all nodes in <math>F</math> that are also in <math>H</math> are all contained in a single edge of <math>H</math>.
| |||