Decomposition method (constraint satisfaction): Difference between revisions

Revision as of 20:30, 3 June 2019

Revision as of 20:51, 3 June 2019

Line 1:

{{More citations needed|date=June 2019}}

In [[constraint satisfaction]], a '''decomposition method''' translates a [[constraint satisfaction problem]] into another constraint satisfaction problem that is binary and [[directed acyclic graph|acyclic]]. Decomposition methods work by grouping variables into sets, and solving a subproblem for each set. These translations are done because solving binary acyclic problems is a [[tractable problem]].