Decomposition Method (constraint Satisfaction)

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 good husband finds method as efficient in the packing of fire-wood in a shed, or in the harvesting of fruits in the cellar, as in Peninsular campaigns or the files of the Department of State.
    Ralph Waldo Emerson (1803–1882)