This HTML5 document contains 133 embedded RDF statements represented using HTML+Microdata notation.

The embedded RDF content will be recognized by any processor of HTML5 Microdata.

Namespace Prefixes

PrefixIRI
n27http://www.dbai.tuwien.ac.at/proj/hypertree/
dcthttp://purl.org/dc/terms/
yago-reshttp://yago-knowledge.org/resource/
dbohttp://dbpedia.org/ontology/
n11http://dbpedia.org/resource/File:
n19http://www.ics.uci.edu/~dechter/books/
foafhttp://xmlns.com/foaf/0.1/
n13http://www.cs.uu.nl/research/projects/treewidthlib/
n23https://global.dbpedia.org/id/
n4http://www.itu.dk/people/sathi/treed/
yagohttp://dbpedia.org/class/yago/
dbthttp://dbpedia.org/resource/Template:
rdfshttp://www.w3.org/2000/01/rdf-schema#
freebasehttp://rdf.freebase.com/ns/
n14https://web.archive.org/web/20060512022851/http:/www.ics.uci.edu/~vgogate/
n10http://commons.wikimedia.org/wiki/Special:FilePath/
dbpedia-fahttp://fa.dbpedia.org/resource/
rdfhttp://www.w3.org/1999/02/22-rdf-syntax-ns#
owlhttp://www.w3.org/2002/07/owl#
wikipedia-enhttp://en.wikipedia.org/wiki/
dbphttp://dbpedia.org/property/
dbchttp://dbpedia.org/resource/Category:
provhttp://www.w3.org/ns/prov#
xsdhhttp://www.w3.org/2001/XMLSchema#
n24http://www.springerlink.com/(rqc54x55rqwetq55eco03ymp)/app/home/contribution.asp%3Freferrer=parent&backto=issue,5,61;journal,1765,3346;linkingpublicationresults,1:
n15http://carlit.toulouse.inra.fr/cgi-bin/awki.cgi/
wikidatahttp://www.wikidata.org/entity/
dbrhttp://dbpedia.org/resource/
n12https://www.springer.com/sgw/cda/frontpage/

Statements

Subject Item
dbr:Decomposition_method_(constraint_satisfaction)
rdf:type
yago:Procedure101023820 yago:YagoPermanentlyLocatedEntity yago:Abstraction100002137 yago:Event100029378 yago:PsychologicalFeature100023100 yago:Activity100407535 yago:Algorithm105847438 yago:Act100030358 yago:WikicatGraphAlgorithms yago:Rule105846932
rdfs:label
Decomposition method (constraint satisfaction)
rdfs:comment
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.
foaf:depiction
n10:Biconnected-components-1.svg n10:Biconnected-components-2.svg n10:Biconnected-components-3.svg n10:Solving-tree-decomposition-1.svg n10:Cutset-1.svg n10:Solving-tree-decomposition-2.svg n10:Cutset-2.svg n10:Solving-tree-decomposition-3.svg n10:Cutset-3.svg n10:Solving-tree-decomposition-4.svg n10:Cutset-4.svg n10:Join-tree-clustering-1.svg n10:Join-tree-clustering-2.svg n10:Passing-constraint.svg n10:Join-tree-clustering-3.svg n10:Tree-decomposition-1-corrected.svg n10:Tree-decomposition-2.svg n10:Tree-decomposition-3.svg n10:Tree-decomposition-4.svg n10:Query-decomposition-1.svg n10:Query-decomposition-2.svg n10:Hyphertree-decomposition.svg
dct:subject
dbc:Constraint_programming
dbo:wikiPageID
4706795
dbo:wikiPageRevisionID
1032115921
dbo:wikiPageWikiLink
dbr:Forest_(graph_theory) dbr:Tree_(graph_theory) dbr:Treewidth dbr:Feedback_vertex_set dbr:Ordered_graph dbr:Tractable_problem dbr:Chordal_graph n11:Query-decomposition-1.svg n11:Query-decomposition-2.svg dbr:Primal_constraint_graph dbr:Hidden_transformation dbr:Junction_tree_algorithm dbr:Anytime_Algorithm dbr:NP-complete n11:Biconnected-components-1.svg dbc:Constraint_programming n11:Biconnected-components-2.svg n11:Biconnected-components-3.svg n11:Cutset-1.svg n11:Cutset-2.svg n11:Cutset-3.svg dbr:Induced_width n11:Cutset-4.svg dbr:Tree_decomposition n11:Passing-constraint.svg dbr:Directional_arc_consistency dbr:Constraint_satisfaction dbr:Constraint_satisfaction_dual_problem dbr:Constraint_satisfaction_problem dbr:Directed_acyclic_graph dbr:Adaptive_consistency n11:Solving-tree-decomposition-1.svg n11:Solving-tree-decomposition-2.svg n11:Solving-tree-decomposition-3.svg n11:Solving-tree-decomposition-4.svg n11:Tree-decomposition-1-corrected.svg n11:Tree-decomposition-2.svg n11:Join-tree-clustering-1.svg n11:Tree-decomposition-3.svg dbr:Bucket_elimination dbr:Biconnected_component n11:Join-tree-clustering-2.svg n11:Tree-decomposition-4.svg n11:Join-tree-clustering-3.svg dbr:Structural_restriction n11:Hyphertree-decomposition.svg dbr:Separating_vertex dbr:P_(complexity) dbr:Join_tree dbr:Binary_constraint dbr:Complexity_of_constraint_satisfaction dbr:Maximal_clique
dbo:wikiPageExternalLink
n4: n12:0,11855,5-0-22-1519914-0,00.html%3Freferer=www.springer.de%2Fcgi-bin%2Fsearch_book.pl%3Fisbn%3D0-387-94883-X n13: n14: n15:ToolBarIntro n19:index.html n24:105633,1 n27:downloads.html
owl:sameAs
dbpedia-fa:روش_تجزیه n23:4j982 freebase:m.0cjbvp wikidata:Q5249566 yago-res:Decomposition_method_(constraint_satisfaction)
dbp:wikiPageUsesTemplate
dbt:More_citations_needed dbt:Cite_conference dbt:Cite_book dbt:Dead_link dbt:Cbignore dbt:Cite_journal dbt:As_of dbt:ISBN
dbo:thumbnail
n10:Tree-decomposition-1-corrected.svg?width=300
dbp:bot
medic
dbp:date
February 2020
dbo:abstract
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.
prov:wasDerivedFrom
wikipedia-en:Decomposition_method_(constraint_satisfaction)?oldid=1032115921&ns=0
dbo:wikiPageLength
43198
foaf:isPrimaryTopicOf
wikipedia-en:Decomposition_method_(constraint_satisfaction)
Subject Item
dbr:Composition_(objects)
dbo:wikiPageWikiLink
dbr:Decomposition_method_(constraint_satisfaction)
Subject Item
dbr:Geometric_constraint_solving
dbo:wikiPageWikiLink
dbr:Decomposition_method_(constraint_satisfaction)
Subject Item
dbr:Constraint_satisfaction_dual_problem
dbo:wikiPageWikiLink
dbr:Decomposition_method_(constraint_satisfaction)
Subject Item
dbr:MRF_optimization_via_dual_decomposition
dbo:wikiPageWikiLink
dbr:Decomposition_method_(constraint_satisfaction)
Subject Item
dbr:Complexity_of_constraint_satisfaction
dbo:wikiPageWikiLink
dbr:Decomposition_method_(constraint_satisfaction)
Subject Item
dbr:Decomposition_method
dbo:wikiPageWikiLink
dbr:Decomposition_method_(constraint_satisfaction)
dbo:wikiPageDisambiguates
dbr:Decomposition_method_(constraint_satisfaction)
Subject Item
dbr:Tree_decomposition
dbo:wikiPageWikiLink
dbr:Decomposition_method_(constraint_satisfaction)
Subject Item
dbr:Dantzig–Wolfe_decomposition
dbo:wikiPageWikiLink
dbr:Decomposition_method_(constraint_satisfaction)
Subject Item
dbr:Fractal-generating_software
dbo:wikiPageWikiLink
dbr:Decomposition_method_(constraint_satisfaction)
Subject Item
dbr:Nicole_Fortin
dbo:wikiPageWikiLink
dbr:Decomposition_method_(constraint_satisfaction)
Subject Item
dbr:Hypertree_decomposition
dbo:wikiPageWikiLink
dbr:Decomposition_method_(constraint_satisfaction)
dbo:wikiPageRedirects
dbr:Decomposition_method_(constraint_satisfaction)
Subject Item
dbr:Join-tree_clustering
dbo:wikiPageWikiLink
dbr:Decomposition_method_(constraint_satisfaction)
dbo:wikiPageRedirects
dbr:Decomposition_method_(constraint_satisfaction)
Subject Item
wikipedia-en:Decomposition_method_(constraint_satisfaction)
foaf:primaryTopic
dbr:Decomposition_method_(constraint_satisfaction)