Decomposition Method (constraint Satisfaction)
In constraint satisfaction, a decomposition method translates a constraint satisfaction problem into another constraint satisfaction problem that is binary and 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.
Read more about Decomposition Method (constraint Satisfaction): Overview, Decomposition Methods, Decomposition Methods For Binary Problems, Decomposition Methods For Arbitrary Problems, Comparison, Solving From A Decomposition, Structural Restrictions, Online Resources
Famous quotes containing the word method:
“... the one lesson in the ultimate triumph of any great actress has been to enforce the fact that a method all technique or a method all throes, is either one or the other inadequate, and often likely to work out in close proximity to the ludicrous.”
—Mrs. Leslie Carter (1862–1937)