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.
- Bot
- enmedic
- Comment
- enIn 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.
- Date
- enFebruary 2020
- Depiction
- Has abstract
- enIn 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.
- Is primary topic of
- Decomposition method (constraint satisfaction)
- Label
- enDecomposition method (constraint satisfaction)
- Link from a Wikipage to an external page
- www.springer.com/sgw/cda/frontpage/0,11855,5-0-22-1519914-0,00.html%3Freferer=www.springer.de%2Fcgi-bin%2Fsearch_book.pl%3Fisbn%3D0-387-94883-X
- www.springerlink.com/(rqc54x55rqwetq55eco03ymp)/app/home/contribution.asp%3Freferrer=parent&backto=issue,5,61;journal,1765,3346;linkingpublicationresults,1:105633,1
- www.dbai.tuwien.ac.at/proj/hypertree/downloads.html
- www.cs.uu.nl/research/projects/treewidthlib/
- www.itu.dk/people/sathi/treed/
- web.archive.org/web/20060512022851/http:/www.ics.uci.edu/~vgogate/
- www.ics.uci.edu/~dechter/books/index.html
- carlit.toulouse.inra.fr/cgi-bin/awki.cgi/ToolBarIntro
- Link from a Wikipage to another Wikipage
- Adaptive consistency
- Anytime Algorithm
- Biconnected component
- Binary constraint
- Bucket elimination
- Category:Constraint programming
- Chordal graph
- Complexity of constraint satisfaction
- Constraint satisfaction
- Constraint satisfaction dual problem
- Constraint satisfaction problem
- Directed acyclic graph
- Directional arc consistency
- Feedback vertex set
- File:Biconnected-components-1.svg
- File:Biconnected-components-2.svg
- File:Biconnected-components-3.svg
- File:Cutset-1.svg
- File:Cutset-2.svg
- File:Cutset-3.svg
- File:Cutset-4.svg
- File:Hyphertree-decomposition.svg
- File:Join-tree-clustering-1.svg
- File:Join-tree-clustering-2.svg
- File:Join-tree-clustering-3.svg
- File:Passing-constraint.svg
- File:Query-decomposition-1.svg
- File:Query-decomposition-2.svg
- File:Solving-tree-decomposition-1.svg
- File:Solving-tree-decomposition-2.svg
- File:Solving-tree-decomposition-3.svg
- File:Solving-tree-decomposition-4.svg
- File:Tree-decomposition-1-corrected.svg
- File:Tree-decomposition-2.svg
- File:Tree-decomposition-3.svg
- File:Tree-decomposition-4.svg
- Forest (graph theory)
- Hidden transformation
- Induced width
- Join tree
- Junction tree algorithm
- Maximal clique
- NP-complete
- Ordered graph
- P (complexity)
- Primal constraint graph
- Separating vertex
- Structural restriction
- Tractable problem
- Tree (graph theory)
- Tree decomposition
- Treewidth
- SameAs
- 4j982
- Decomposition method (constraint satisfaction)
- m.0cjbvp
- Q5249566
- روش تجزیه
- Subject
- Category:Constraint programming
- Thumbnail
- WasDerivedFrom
- Decomposition method (constraint satisfaction)?oldid=1032115921&ns=0
- WikiPageLength
- 43198
- Wikipage page ID
- 4706795
- Wikipage revision ID
- 1032115921
- WikiPageUsesTemplate
- Template:As of
- Template:Cbignore
- Template:Cite book
- Template:Cite conference
- Template:Cite journal
- Template:Dead link
- Template:ISBN
- Template:More citations needed
