Content deleted Content added
m math typo |
Citation bot (talk | contribs) Added isbn. | Use this bot. Report bugs. | Suggested by Abductive | Category:Graph minor theory | #UCB_Category 20/33 |
||
| (6 intermediate revisions by 6 users not shown) | |||
Line 5:
In [[graph theory]], a '''tree decomposition''' is a mapping of a [[Graph (discrete mathematics)|graph]] into a [[tree (graph theory)|tree]] that can be used to define the [[treewidth]] of the graph and speed up solving certain computational problems on the graph.
Tree decompositions are also called '''junction trees''', '''clique trees''', or '''join trees'''. They play an important role in problems like [[belief propagation|probabilistic inference]], [[constraint satisfaction]], [[query optimization]],{{
The concept of tree decomposition was originally introduced by {{harvs|last=Halin|first=Rudolf|authorlink=Rudolf Halin|year=1976|txt}}. Later it was rediscovered by {{harvs|first1=Neil|last1=Robertson|author1-link=Neil Robertson (mathematician)|first2=Paul|last2=Seymour|author2-link=Paul Seymour (mathematician)|year=1984|txt}} and has since been studied by many other authors.<ref>{{harvtxt|Diestel|2005}} pp.354–355</ref>
Line 24:
A tree decomposition {{math|1=(''X'', ''T'' = (''I'', ''F''))}} of treewidth {{mvar|k}} is ''smooth'', if for all <math>i \in I : |X_i| = k + 1</math>, and for all <math>(i, j) \in F : |X_i \cap X_j| = k</math>.<ref name="b96">{{harvtxt|Bodlaender|1996}}.</ref>
==Treewidth==
Line 34 ⟶ 32:
It is NP-complete to determine whether a given graph {{mvar|G}} has treewidth at most a given variable {{mvar|k}}.<ref>{{harvtxt|Arnborg|Corneil|Proskurowski|1987}}.</ref>
However, when {{mvar|k}} is any fixed constant, the graphs with treewidth {{mvar|k}} can be recognized, and a width {{mvar|k}} tree decomposition constructed for them, in linear time.<ref name="b96"
==Dynamic programming==
Line 51 ⟶ 49:
*[[Bramble (graph theory)|Brambles]] and [[Haven (graph theory)|havens]]{{snd}}Two kinds of structures that can be used as an alternative to tree decomposition in defining the treewidth of a graph.
*[[Branch-decomposition]]{{snd}}A closely related structure whose width is within a constant factor of treewidth.
*[[
==Notes==
Line 92 ⟶ 90:
| series = Lecture Notes in Computer Science
| volume = 317 | year = 1988 | pages = 105–118
| doi = 10.1007/3-540-19488-6_110| hdl = 1874/16258 | isbn = 978-3-540-19488-0 | hdl-access = free}}.
*{{citation
| last = Bodlaender | first = Hans L. | authorlink = Hans L. Bodlaender
Line 107 ⟶ 105:
| url=http://www.math.uni-hamburg.de/home/diestel/books/graph.theory/
}}.
*{{citation
| last1 = Gottlob | first1 = Georg
| last2 = Lee | first2 = Stephanie Tien
| last3 = Valiant | first3 = Gregory
| last4 = Valiant | first4 = Paul
| doi = 10.1145/2220357.2220363
| issue = 3
| journal = [[Journal of the ACM]]
| mr = 2946220
| page = A16:1–A16:35
| title = Size and treewidth bounds for conjunctive queries
| volume = 59
| year = 2012}}
*{{Citation
| title = ''S''-functions for graphs
Line 114 ⟶ 125:
| pages = 171–186
| volume = 8
| issue = 1–2
| doi=10.1007/BF01917434
| s2cid = 120256194
}}.
*{{citation
| last1 = Robertson | first1 = Neil | authorlink1 = Neil Robertson (mathematician)
| last2 = Seymour | first2 = Paul D. | authorlink2 = Paul Seymour (mathematician)
| title = Graph minors III: Planar tree-width
| journal = [[Journal of Combinatorial Theory
| volume = 36
| issue = 1 | year = 1984 | pages = 49–64
| |||