Content deleted Content added
Waldyrious (talk | contribs) →Online Resources: «"Anytime Algorithm" → "Anytime Algorithm"» |
Diego Moya (talk | contribs) Disambiguation of reference |
||
Line 1:
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]].
Each structural restriction defined a measure of complexity of solving the problem after conversion; this measure is called ''width''. Fixing a maximal allowed width is a way for identifying a subclass of constraint satisfaction problems. Solving problems in this class is polynomial for most decompositions; if this holds for a decomposition, the class of fixed-width problems form a tractable subclass of constraint satisfaction problems.
| |||