Decomposition method (constraint satisfaction): Difference between revisions

Revision as of 12:04, 28 August 2017

Revision as of 01:04, 9 January 2018

Line 104:

===Cycle hypercutset===

This is the same mathodmethod of cycle cutset using the definition of cutset for hypergraphs: a cycle hypercutset of a hypergraph is a set of edges (rather than vertices) that makes the hypergraph acyclic when all their vertices are removed. A decomposition can be obtained by grouping all variables of a hypercutset in a single one. This leads to a tree whose nodes are sets of hyperedges. The width of such a decomposition is the maximal size of the sets associated with nodes, which is one if the original problem is acyclic and the size of its minimal hypercutset otherwise. The width of a problem is the minimal width of its decompositions.

===Hinge decomposition===