查看“︁树宽”︁的源代码

[[图论]]中，[[无向图]]的'''树宽'''（treewidth）是描述图与[[树 (图论)|树]]的距离的正[[整数]]。树宽为1的图就是树或[[树_(图论)#森林|森林]]。树宽不大于2的图叫做[[系列并行图]]。树宽恰为''k''的最大图称作[[k树]]，树宽不大于''k''的图称作[[部分k树]]。很多有充分研究的图族的树宽也是有界的。

树宽可用几种等价方式正式定义：图的[[树分解]]中最大顶点集的大小、图的[[弦补全]]中最大[[团 (图论)|团]]的大小、描述图上[[追逃对策]]的[[港 (图论)|港]]的最大阶数、[[刺藤 (图论)|刺藤]]（bramble，相互接触的连通子图的集合）的最大阶数。

树宽常用作图[[算法]]的[[参数复杂性]]分析中的参数。对一般图[[NP困难]]的许多算法，将树宽固定于常数时就变得容易了。

树宽的概念最初由{{harvs|last1 = Bertelè|first1=Umberto|last2=Brioschi|first2=Francesco|year = 1972|txt}}提出，叫做“维度”（dimension）。后来，{{harvs|last=Halin|first=Rudolf|authorlink=Rudolf Halin|year=1976|txt}}根据树宽和[[哈德维格数]]的共同属性，重新发现了树宽。{{harvs|first1=Neil|last1=Robertson|author1-link=Neil Robertson (mathematician)|first2=Paul|last2=Seymour|author2-link=Paul Seymour (mathematician)|year=1984|txt}}又重新发现了树宽，自此才获得了学界的关注。<ref>{{harvtxt|Diestel|2005}}</ref>{{rp|354–355}}

==定义==
[[Image:Tree decomposition.svg|thumb|240px|将8顶点图分解为6结点树的树分解。边两端的两顶点在树的某个结点排列在一起，每个图顶点则在连续子树的结点上排列。树结点最多列出3个顶点，因此该分解的宽为2。]]

图<math>G=(V,\ E)</math>的[[树分解]]是结点为<math>X_1,\ \dots,\ X_n</math>的树''T''，其中<math>X_i</math>都是''V''的子集，满足下列性质<ref>{{harvtxt|Diestel|2005}} section 12.3</ref>（为避免与''G''的顶点混淆，“结点”仅指树''T''的顶点）：
# <math>\bigcup_i X_i=V.</math>即，图顶点至少包含在一个树结点中。
# 若<math>X_i,\ X_j</math>共同包含顶点''v''，则在<math>X_i</math>到<math>X_j</math>的（唯一）路径上，''T''的所有结点<math>X_k</math>也都包含''v''。即，包含顶点''v''的树结点构成''T''的连通子树。
# 对图中每条边<math>(v,\ w)</math>，存在同时包含''v''、''w''的子集<math>X_i</math>。即，只有当相应的子树有共同结点时，图顶点才是相邻的。
树分解的宽是其最大集<math>X_i</math>的大小减一。图''G''的'''树宽'''<math>{\rm tw}(G)</math>等于''G''的树分解的最小宽度，按这定义，最大集的大小减一，树的树宽才能等于一。

等价地，''G''的树宽等于[[最大团|团数]]最小的含''G''[[弦图]]中最大[[团 (图论)|团]]的大小减一。在''G''中属于<math>X_i</math>的两顶点间添加一条边，就可得到团大小相符的弦图。

树宽也可用[[港 (图论)|港]]描述，其是在图上定义的[[追逃对策]]中逃逸策略的函数。若有至多<math>k+1</math>阶的港——函数<math>\beta</math>，将''G''中最多''k''个顶点的集合''X''映射到<math>G\backslash X</math>的一个连通分量中，并且具有<math>X\subseteq Y\Rightarrow \beta(Y)\subseteq\beta(X)</math>的[[单调性]]，就称图''G''的树宽为''k''。

[[File:3x3 grid graph haven.svg|thumb|3&times;3格图中的4阶[[刺藤 (图论)|刺藤]]，其存在表明图的树宽至少为3]]
使用[[刺藤 (图论)|刺藤]]（bramble）也可做出类似描述。刺藤是指一族相互接触的连通子图（即共享一个顶点，或由一条边连接）。<ref>{{harvtxt|Seymour|Thomas|1993}}.</ref>刺藤的阶数是子图族的最小[[集合覆盖问题|命中集]]（hitting set），图的树宽等于刺藤最大阶数减一。

==例子==
[[完全图]]<math>K_n</math>的树宽为<math>n-1</math>。这用树宽的弦图定义很容易看出来：完全图已经是弦图，添加更多边不能减小最大团的大小。

当且仅当至少2顶点的连通图是树，连通图的树宽为1。树的树宽为1，与完全图同理（即它已经是弦图，且最大团大小为2）。反之，若图中有循环，则所有[[弦补全]]都至少包括一个由循环的3个连续顶点组成的三角形，由此可见其树宽至少为2。

==有界树宽==
===有界树宽图族===
树宽不大于常数''k''的图称作[[部分k树]]。其他具有有界树宽的图族，有[[仙人掌图]]、[[伪森林]]、[[系列并行图]]、[[外平面图]]、[[哈林图]]、[[阿波罗尼奥斯网络]]等。<ref name="b98">{{harvtxt|Bodlaender|1998}}.</ref>在[[结构化编程]]的[[编译]]阶段出现的[[控制流图]]，树宽也是有界的，使[[寄存器配置]]之类任务可在其上高效执行。<ref>{{harvtxt|Thorup|1998}}.</ref>

[[平面图]]的树宽不一定有界，因为<math>n\times n</math>[[格图]]是树宽恰为''n''的平面图。于是，若''F''是树宽有界的[[图子式|子式]]闭图族，则它不可能包含所有平面图。反之，若某平面图不能作为''F''族中图的子式出现，则存在常数''k''，使''F''中所有图的树宽不大于''k''。即，以下3个条件等价：<ref>{{harvtxt|Robertson|Seymour|1986}}.</ref>
# ''F''是树宽有界图的子式闭图族；
# 表征了''F''的有限多禁子式（forbidden minor）中，有一个是平面的；
# ''F''是不含平面图的子式闭图族。

===禁子式===
[[File:Partial 3-tree forbidden minors.svg|thumb|300px|树宽为3的4个禁子式：<math>K_5</math>（左上）、八面体图（左下）、瓦格纳图（右上）、五棱柱图（右下）]]

对每个有限值''k''，树宽不大于''k''的图都可用[[禁图特征|禁子式]]的有限集表示（即，任意树宽大于''k''的图，都包含集合中的一个图作为子式）。每个这样的禁子式集都包含平面图。
* 对于<math>k=1</math>，唯一的禁子式是3-顶点[[循环图]]。<ref name="b88">{{harvtxt|Bodlaender|1988}}.</ref>
* 对于<math>k=2</math>，唯一的禁子式是4-顶点[[完全图]]<math>K_4</math>。<ref name="b88"/>
* 对于<math>k=3</math>，有4个禁子式：<math>K_5</math>、[[八面体]]图、[[五棱柱]]图、[[瓦格纳图]]。其中两个[[多面体图]]是平面图。<ref>{{harvtxt|Arnborg|Proskurowski|Corneil|1990}}; {{harvtxt|Satyanarayana|Tung|1990}}.</ref>
对更大的''k''，禁子式的增长速度不小于''k''的平方根指数。{{sfnp|Ramachandramurthi|1997}}但已知的禁子式的大小与数量的上界远高于这个下界。{{sfnp|Lagergren|1993}}

==算法==
===计算树宽===
判断给定图''G''的树宽是否不大于给定值''k''的问题，是NP完全的。{{sfnp|Arnborg|Corneil|Proskurowski|1987}}而当''k''为任意固定常数时，可在线性时间内识别出树宽为''k''的图，并为之构造出树宽为''k''的树分解。<ref name="b96">{{harvtxt|Bodlaender|1996}}.</ref>这算法的耗时对''k''是指数级的。

由于树宽在众多领域中的作用，人们开发了计算树宽的各种算法。根据具体的应用，我们可以选择更好的近似率，或运行时间与输入或树宽大小更相关的算法。
下表概述了一些树宽算法。其中，''k''是树宽，''n''是输入图''G''的顶点数。每种算法都能在<math>f(k)\cdot g(n)</math>的时间内输出宽度等于“近似”栏中的分解图。例如，{{harvtxt|Bodlaender|1996}}的算法在<math>2^{O(k^3)}\cdot n</math>时间内，要么为输入图''G''构建树宽不大于''k''的树分解，要么报告''G''的树宽大于''k''。相似地，{{harvtxt|Bodlaender|Drange|Dregi|Fomin|2016}}的算法在<math>2^{O(k)}\cdot n</math>时间内，要么为输入图''G''构建树宽不大于<math>5k+4</math>的树分解，要么报告''G''的树宽大于''k''。{{harvtxt|Korhonen|2021}}在同样运行时间内，将其改进到<math>2k+1</math>。

{| class="wikitable"
|-
! 近似 !! <math>f(k)</math> !! <math>g(n)</math> !! 参考文献
|-
| 精确 || <math>O(1)</math> || <math>O(n^{k+2})</math> || {{harvtxt|Arnborg|Corneil|Proskurowski|1987}}
|-
|  <math>4k+3</math>  || <math>O(3^{3k})</math> || <math>O(n^2)</math> || {{harvtxt|Robertson|Seymour|1995}}
|-
| <math>8k+7</math> || <math>2^{O(k\log k)}</math> || <math>n\log^2n</math> || {{harvtxt|Lagergren|1996}}
|-
| <math>5k+4\text{或}7k+6</math> || <math>2^{O(k\log k)}</math> || <math>n\log n</math> || {{harvtxt|Reed|1992}}
|-
|  精确 || <math>2^{O(k^3)}</math> || <math>O(n)</math> ||{{harvtxt|Bodlaender|1996}}
|-
|  <math>O \left( k \cdot \sqrt{\log k} \right)</math> || <math>O(1)</math> || <math>n^{O(1)}</math> ||{{harvtxt|Feige|Hajiaghayi|Lee |2008}}
|-
|  <math>4.5k+4</math> || <math>2^{3k}</math> || <math>n^2</math> ||{{harvtxt|Amir |2010}}
|-
|  <math>\frac{11}{3}k+4</math> || <math>2^{3.6982k}</math> || <math>n^3\log^4n</math> ||{{harvtxt|Amir |2010}}
|-
|  精确 || <math>O(1)</math> || <math>O(1.7347^n)</math> || {{harvtxt|Fomin|Todinca|Villanger|2015}}
|-
|  <math>3k+2</math>  || <math>2^{O(k)}</math> || <math>O(n\log n)</math> || {{harvtxt|Bodlaender|Drange|Dregi|Fomin|2016}}
|-
|  <math>5k+4</math>  || <math>2^{O(k)}</math> || <math>O(n)</math> || {{harvtxt|Bodlaender|Drange|Dregi|Fomin|2016}}
|-
|  <math>k^2</math> || <math>O(k^7)</math> || <math>O(n\log n)</math> || {{harvtxt|Fomin|Lokshtanov|Saurabh| Pilipczuk |2018}}
|-
|  <math>5k+4</math>  || <math>2^{8.765k}</math> || <math>O(n\log n)</math> || {{harvtxt|Belbasi|Fürer|2021a}}
|-
| <math>2^{O(k)}</math> || <math>2^{O(k)}</math> || <math>O(n)</math> || {{harvtxt|Korhonen|2021}} 
|-
|  <math>5k+4</math>  || <math>2^{6.755k}</math> || <math>O(n\log n)</math> || {{harvtxt|Belbasi|Fürer|2021b}}
|-
|  精确  || <math>2^{O(k^2)}</math> || <math>n^4</math> || {{harvtxt|Korhonen|Lokshtanov|2022}}
|-
|  <math>(1+\varepsilon)k</math>  || <math>k^{O(k/\varepsilon)}</math> || <math>n^4</math> || {{harvtxt|Korhonen|Lokshtanov|2022}}
|-
|}

{{unsolved|数学|[[平面图 (图论)|平面图]]的树宽能否在多项式时间内算得？}}
目前还不知道确定[[平面图 (图论)|平面图]]树宽的问题是不是NP完全的，也不知道其树宽能否在多项式时间内计算出来。{{sfnp|Kao|2008}}

实践中，{{harvtxt|Shoikhet|Geiger|1997}}的算法可以确定顶点数最多为100、树宽最多为11的图的树宽，并以最优树宽找到这些图的弦补全。

对更大的图，可以用基于搜索的技术，如[[分支定界]]搜索（BnB）与[[最佳优先搜索]]，以计算树宽。它们是[[任意时间算法]]，提前停止时会输出树宽的上界。

第一个计算树宽的BnB算法叫做QuickBB算法<ref>{{Cite web |title=Vibhav Gogate |url=https://personal.utdallas.edu/~vibhav.gogate/quickbb.html |access-date=2022-11-27 |website=personal.utdallas.edu |archive-date=2022-11-27 |archive-url=https://web.archive.org/web/20221127050627/https://personal.utdallas.edu/~vibhav.gogate/quickbb.html |dead-url=no }}</ref>，是Gogate与Dechter提出的。<ref name=":0">{{Cite arXiv |last1=Gogate |first1=Vibhav |last2=Dechter |first2=Rina |date=2012-07-11 |title=A Complete Anytime Algorithm for Treewidth |class=cs.DS |eprint=1207.4109 }}</ref>BnB算法的质量在很大程度上取决于所用下限的质量，Gogate与Dechter<ref name=":0" />还提出了一种计算树宽下界的新算法，称作minor-min-width。<ref name=":0" />图的树宽绝不大于最小[[度 (图论)|度数]]或其[[图子式]]，minor-min-width算法利用这一事实，在高层次上得出了树宽的下界。minor-min-width算法通过收缩最小度顶点与邻顶点间的边，反复构造[[图子式]]，直到仅剩一个顶点。所构造子式中，最小度的最大值是图树宽的下界。

Dow、Korf<ref>{{Cite web |title=Best-First Search for Treewidth |url=https://www.aaai.org/Library/AAAI/2007/aaai07-182.php |access-date=2022-11-27 |website=www.aaai.org |archive-date=2022-01-22 |archive-url=https://web.archive.org/web/20220122053431/https://www.aaai.org/Library/AAAI/2007/aaai07-182.php |dead-url=no }}</ref>使用[[最佳优先搜索]]改进了QuickBB算法，在某些图上快了一个数量级。

===解小树宽图上的其他问题===
20世纪70年代初，人们发现，只要图的“维度”有界，就可通过非序列[[动态规划]]，高效解决一大类定义在图上的组合优化问题{{sfnp|Bertelè|Brioschi|1972}}。{{harvtxt|Bodlaender|1998}}的研究表明，“维度”等同于树宽。后来，多名学者在80年代末独立观察到，<ref>{{harvtxt|Arnborg|Proskurowski|1989}}; {{harvtxt|Bern|Lawler|Wong|1987}}; {{harvtxt|Bodlaender|1988}}.</ref>很多对任意图来说[[NP完全性|NP完全]]的问题，对树宽有界的图来说，可用[[动态规划]]，利用树分解高效解决。
举例来说，''k''树宽图的[[图着色问题|着色问题]]可通过对树分解使用[[动态规划]]算法解决。将<math>X_i</math>（树分解的所有集合）的顶点[[集合划分|划分]]为颜色类，算法会结合储存在结点的相似类信息确定着色是否有效、扩展到树分解中所有的子结点。由此产生的算法能在<math>O(k^{k+O(1)}n)</math>时间内找到''n''顶点图的最优着色，这个时间约能束使问题[[固定参数可解]]。

===古赛尔定理===
{{main|古赛尔定理}}
对于一大类问题，如果提供具有有界常值树宽的[[树分解]]，就可用线性时间算法求解。具体来说，[[古赛尔定理]]<ref>{{harvtxt|Courcelle|1990}}; {{harvtxt|Courcelle|1992}}</ref>指出，若图问题可用[[一元二阶逻辑]]表为[[图的逻辑]]，就可在树宽有界图上用线性时间求解。一元二阶逻辑是一种描述图属性的语言，有下列结构：
* 逻辑运算，如<math> \wedge ,\vee ,\neg ,\Rightarrow </math>
* 成员检验，如<math>e\in E,\ v\in V</math>
* 对顶点、边、顶点集和/或边集的量词，如<math>\forall v\in V,\ \exists e\in E,\ \exists I\subseteq V,\ \forall F\subseteq E</math>
* 邻接检验（如''u''是''e''的端点），及一些允许优化的扩展。
例如，考虑[[图着色问题|3着色问题]]。对图<math>G=(V,\ E)</math>，此问题是说，有没有可能为每个顶点<math>v\in V</math>分配3种颜色中的一种，使得相邻顶点总被分配不同颜色。
这个问题用一元二阶逻辑表为：
:<math> \exists W_1 \subseteq V : \exists W_2 \subseteq V : \exists W_3 \subseteq V : \forall v \in V : (v \in W_1 \vee v \in W_2 \vee v \in W_3) \wedge </math>
:<math> \forall v \in V : \forall w \in V : (v,w) \in E \Rightarrow (\neg (v \in W_1 \wedge w \in W_1) \wedge \neg (v \in W_2 \wedge w \in W_2) \wedge \neg (v \in W_3 \wedge w \in W_3))</math>, 
其中<math>W_1,\ W_2,\ W_3</math>分别代表3种颜色的顶点子集。于是，根据古赛尔定理，对具有有界常值树宽的树分解的给定图，3着色问题可在线性时间内求解。

==相关参数==
===径宽===
图的[[径宽]]也是经过树分解定义的，不过其底树是[[道路 (图论)|径图]]，也可通过[[区间图]]定义，类似于由弦图定义树宽。因此，图的径宽总不小于树宽，但只能比树宽大一个对数因子。<ref name="b98"/>另一个参数是[[带宽 (图论)|带宽]]，其定义与[[紧合区间图]]类似，径宽是其下界。其他相关参数还有[[树深]]，当且仅当子式闭图族中包含路径时有界；以及[[退化度]]，这是衡量图稀疏程度的指标，最多等于树宽。

===格子式大小===
由于<math>n\times n</math>[[格图]]的树宽为''n''，图''G''的树宽总大于等于''G''的最大方格[[图子式|子式]]的大小。在另一个方向上，Robertson与Seymour的格子式定理表明，存在无界函数''f''使得最大方格子式的大小至少为<math>f(r)</math>，其中''r''是树宽。<ref>Robertson, Seymour. ''Graph minors. V. Excluding a planar graph''. [http://www.sciencedirect.com/science/article/pii/0095895686900304] {{Wayback|url=http://www.sciencedirect.com/science/article/pii/0095895686900304 |date=20240130141351 }} {{Open access}}</ref>''f''的已知最佳区间：对某常数<math>d>0</math>，下界为<math>\Omega(r^d)</math>，上界为<ref>{{harvtxt|Chekuri|Chuzhoy|2016}}</ref>
:<math>O \left( \sqrt{ r / \log r} \right).</math>

关于下界中的Ω记号，见[[大O符号]]。对有约束的图族，区间也更严。[[双维理论]]为这些图族上的很多图优化问题提供了高效算法。{{sfnp|Demaine|Hajiaghayi|2008}}
[[哈林格定理]]提供了无限图的树宽与格子式大小关系的类比。{{sfnp|Diestel|2004}}

===直径与局部树宽===
若图族''F''在取子图下封闭，其中图的树宽有以[[距离_(图论)#相关概念|直径]]为函数的上界，则称它们具有'''有界局部树宽'''或'''直径树宽性'''。若假设该族在取[[图子式]]下也封闭，则当且仅当''F''的一个禁子式是[[顶点图]]（apex graph），''F''才有有界的局部树宽。{{sfnp|Eppstein|2000}}这一结果的最初证明显示，无顶点子式图族的树宽作为直径的函数，最多呈2倍指数增长；<ref>{{harvtxt|Eppstein|2000}}; {{harvtxt|Demaine|Hajiaghayi|2004a}}.</ref>后来降为单倍指数增长{{sfnp|Demaine|Hajiaghayi|2008}}，最后抵达线性的界。{{sfnp|Demaine|Hajiaghayi|2004b}}有界局部树宽与[[双维理论]]密切相关，<ref>{{harvtxt|Demaine|Fomin|Hajiaghayi|Thilikos|2004}}; {{harvtxt|Demaine|Hajiaghayi|2008}}.</ref>一阶逻辑中可定义的图属性都可用略微超线性的时间来决定一个无顶点子式图族。 {{sfnp|Frick|Grohe|2001}}

对取子式不封闭的图族，也有可能具有有界的局部树宽。特别是对一族有界度图来说，这是一定成立的，因为有界直径子图的大小有界。另一个例子是1-平面图，即可在平面上绘制的、每条边有1交叉的图，以及更广义地说，可在亏格有界的曲面上绘制的、每条边有一定交叉点的图。与局部树宽有界的子式闭图族一样，这一特征为图的高效近似算法指明了方向。{{sfnp|Grigoriev|Bodlaender|2007}}

===哈德维格数与''S''函数===
{{harvtxt|Halin|1976}}定义了一类叫做“''S''-函数”的图参数，其中包括树宽。这些函数从图映射到整数，[[无边图]]映射到0，具有子式单调性（若对函数''f''、''G''的子式''H''，总有<math>f(H)\le f(G)</math>，则称''f''是“子式单调”的），在[[完全点|与所有现有顶点相邻的位置]]添加新顶点时，函数值加1，并从[[团 (图论)|团]][[顶点分隔|分隔]]两侧的两子图中取较大值。所有此种函数的集合在逐元素最小、最大化运算下，形成了[[完全格]]，当中的顶元素是树宽，底元素是[[哈德维格数]]，即给定图中最大[[完全图|完全]][[图子式|子式]]的大小。

==注释==
{{reflist|30em}}

==参考文献==
{{refbegin|30em}}
*{{citation
 | last = Amir | first = Eyal
 | doi = 10.1007/s00453-008-9180-4
 | issue = 4
 | journal = [[Algorithmica]]
 | mr = 2581059
 | pages = 448–479
 | title = Approximation algorithms for treewidth
 | volume = 56
 | year = 2010| s2cid = 5874913
 }}.
*{{citation
 | last1 = Arnborg | first1 = S.
 | last2 = Corneil | first2 = D. | author2-link = Derek Corneil
 | last3 = Proskurowski | first3 = A.
 | title = Complexity of finding embeddings in a {{nowrap|<math>k</math>-tree}}
 | journal = [[SIAM Journal on Matrix Analysis and Applications]]
 | volume = 8 | issue = 2 | year = 1987 | pages = 277–284 | doi = 10.1137/0608024}}.
*{{citation
 | last1 = Arnborg | first1 = Stefan
 | last2 = Proskurowski | first2 = Andrzej
 | last3 = Corneil | first3 = Derek G. | author3-link = Derek Corneil
 | doi = 10.1016/0012-365X(90)90292-P
 | issue = 1
 | journal = [[Discrete Mathematics (journal)|Discrete Mathematics]]
 | mr = 1045920
 | pages = 1–19
 | title = Forbidden minors characterization of partial 3-trees
 | volume = 80
 | year = 1990| doi-access = free
 }}.
*{{citation
 | last1 = Arnborg | first1 = S.
 | last2 = Proskurowski | first2 = A.
 | title = Linear time algorithms for NP-hard problems restricted to partial {{nowrap|<math>k</math>-trees}}
 | journal = [[Discrete Applied Mathematics]]
 | volume = 23 | issue = 1 | year = 1989 | pages = 11–24 | doi = 10.1016/0166-218X(89)90031-0| doi-access = free }}.
*{{citation
 | last1 = Belbasi | first1 = Mahdi
 | last2 = Fürer | first2 = Martin
 | editor1-last = Uehara | editor1-first = Ryuhei
 | editor2-last = Hong | editor2-first = Seok-Hee | editor2-link = Seok-Hee Hong
 | editor3-last = Nandy | editor3-first = Subhas C.
 | arxiv = 2010.03105
 | contribution = An improvement of Reed's treewidth approximation
 | doi = 10.1007/978-3-030-68211-8_14
 | mr = 4239527
 | pages = 166–181
 | publisher = Springer
 | series = Lecture Notes in Computer Science
 | title = WALCOM: Algorithms and Computation – 15th International Conference and Workshops, WALCOM 2021, Yangon, Myanmar, February 28 - March 2, 2021, Proceedings
 | volume = 12635
 | year = 2021a| s2cid = 222177100
 }}.
*{{citation
 | last1 = Belbasi | first1 = Mahdi
 | last2 = Fürer | first2 = Martin
 | editor1-last = Du | editor1-first = Ding-Zhu
 | editor2-last = Du | editor2-first = Donglei
 | editor3-last = Wu | editor3-first = Chenchen
 | editor4-last = Xu | editor4-first = Dachuan
 | arxiv = 2111.02614
 | contribution = Finding all leftmost separators of size <math>\le k</math>
 | doi = 10.1007/978-3-030-92681-6_23
 | pages = 273–287
 | publisher = Springer
 | series = Lecture Notes in Computer Science
 | title = Combinatorial Optimization and Applications - 15th International Conference, COCOA 2021, Tianjin, China, December 17-19, 2021, Proceedings
 | volume = 13135
 | year = 2021b| s2cid = 242758210
 }}
*{{citation
 | last1 = Bern | first1 = M. W.
 | last2 = Lawler | first2 = E. L. | author2-link = Eugene Lawler
 | last3 = Wong | first3 = A. L.
 | title = Linear-time computation of optimal subgraphs of decomposable graphs
 | journal = Journal of Algorithms
 | volume = 8 | issue = 2 | year = 1987 | pages = 216–235 | doi = 10.1016/0196-6774(87)90039-3}}.
*{{citation
 | last1 = Bertelè
 | first1 = Umberto
 | last2 = Brioschi
 | first2 = Francesco
 | title = Nonserial Dynamic Programming
 | year = 1972
 | publisher = Academic Press
 | isbn = 978-0-12-093450-8
 | pages = 37–38
 | url = https://books.google.com/books?id=baw3LMwm-y8C&pg=PA37
 | accessdate = 2024-01-30
 | archive-date = 2024-01-30
 | archive-url = https://web.archive.org/web/20240130153538/https://books.google.com/books?id=baw3LMwm-y8C&pg=PA37
 | dead-url = no
 }}.
*{{citation
 | last = Bodlaender | first = Hans L. | author-link = Hans L. Bodlaender
 | contribution = Dynamic programming on graphs with bounded treewidth
 | title = Proc. 15th International Colloquium on Automata, Languages and Programming
 | publisher = Springer-Verlag
 | series = Lecture Notes in Computer Science
 | volume = 317 | year = 1988 | pages = 105–118
 | doi = 10.1007/3-540-19488-6_110| citeseerx = 10.1.1.18.8503| isbn = 978-3-540-19488-0 }}.
*{{citation
 | last = Bodlaender | first = Hans L. | author-link = Hans L. Bodlaender
 | title = A linear time algorithm for finding tree-decompositions of small treewidth
 | journal = [[SIAM Journal on Computing]]
 | volume = 25 | issue = 6 | year = 1996 | pages = 1305–1317 | doi = 10.1137/S0097539793251219| citeseerx = 10.1.1.19.7484}}.
*{{citation
 | last = Bodlaender | first = Hans L. | author-link = Hans L. Bodlaender
 | title = A partial ''k''-arboretum of graphs with bounded treewidth
 | journal = Theoretical Computer Science
 | volume = 209 | issue = 1–2 | pages = 1–45 | year = 1998 | doi = 10.1016/S0304-3975(97)00228-4 | doi-access=free}}.
*{{citation
 | last1 = Bodlaender| first1 = Hans L.
 | last2 = Drange| first2 = Pal G.  
 | last3 = Dregi| first3 = Markus S.
 | last4 = Fomin| first4 = Fedor V.
 | last5 = Lokshtanov| first5 = Daniel
 | last6 = Pilipczuk| first6 = Michal
 | title = A <math>c^k n</math> 5-approximation algorithm for treewidth
 | journal = [[SIAM Journal on Computing]]
 | volume = 45
 | issue = 2 
 | year = 2016 
 | pages = 317–378 
 | doi = 10.1137/130947374| arxiv = 1304.6321}}.
*{{citation
 | last1 = Chekuri | first1 = Chandra
 | last2 = Chuzhoy | first2 = Julia | author2-link = Julia Chuzhoy
 | arxiv=1305.6577
 | doi = 10.1145/2820609
 | issue = 5
 | journal = [[Journal of the ACM]]
 | mr = 3593966
 | pages = A40:1–65
 | title = Polynomial bounds for the grid-minor theorem
 | volume = 63
 | year = 2016| s2cid = 209860422
 }}.
*{{citation|title = The monadic second-order logic of graphs I: Recognizable sets of finite graphs|last = Courcelle|first = B.|date = 1990|journal = [[Information and Computation]]|doi = 10.1016/0890-5401(90)90043-h|volume = 85|pages = 12–75|citeseerx = 10.1.1.158.5595}}.
*{{citation|title = The monadic second-order logic of graphs III: Treewidth, forbidden minors and complexity issues.|last = Courcelle|first = B.|date = 1992|journal = Informatique Théorique|pages = 257–286|issue = 26}}.
*{{citation
 | last1 = Demaine | first1 = Erik D. | author1-link = Erik Demaine
 | last2 = Fomin | first2 = Fedor V.
 | last3 = Hajiaghayi | first3 = MohammadTaghi
 | last4 = Thilikos | first4 = Dimitrios M.
 | year = 2004
 | doi = 10.1137/S0895480103433410
 | issue = 3
 | journal = [[SIAM Journal on Discrete Mathematics]]
 | mr = 2134412
 | pages = 501–511
 | title = Bidimensional parameters and local treewidth
 | volume = 18| citeseerx = 10.1.1.107.6195| s2cid = 7803025 }}.
*{{citation
 | last1 = Demaine | first1 = Erik D. | author1-link = Erik Demaine
 | last2 = Hajiaghayi | first2 = MohammadTaghi
 | doi = 10.1007/s00453-004-1106-1
 | issue = 3
 | journal = [[Algorithmica]]
 | mr = 2080518
 | pages = 211–215
 | title = Diameter and treewidth in minor-closed graph families, revisited
 | volume = 40
 | year = 2004a| s2cid = 390856 }}.
*{{citation
 | last1 = Demaine | first1 = Erik D.
 | last2 = Hajiaghayi | first2 = MohammadTaghi
 | contribution = Equivalence of local treewidth and linear local treewidth and its algorithmic applications
 | location = New York
 | mr = 2290974
 | pages = 840–849
 | publisher = ACM
 | title = Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms
 | year = 2004b}}.
*{{citation
 | last1 = Demaine
 | first1 = Erik D.
 | author1-link = Erik Demaine
 | last2 = Hajiaghayi
 | first2 = MohammadTaghi
 | doi = 10.1007/s00493-008-2140-4
 | issue = 1
 | journal = [[Combinatorica]]
 | pages = 19–36
 | title = Linearity of grid minors in treewidth with applications through bidimensionality
 | url = http://erikdemaine.org/papers/GridMinors_Combinatorica/paper.pdf
 | volume = 28
 | year = 2008
 | s2cid = 16520181
 | accessdate = 2024-01-30
 | archive-date = 2020-10-11
 | archive-url = https://web.archive.org/web/20201011115400/http://erikdemaine.org/papers/GridMinors_Combinatorica/paper.pdf
 | dead-url = no
 }}.
*{{citation
 | last = Diestel | first = Reinhard
 | doi = 10.1007/BF02941538
 | journal = Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg
 | mr = 2112834
 | pages = 237–242
 | title = A short proof of Halin's grid theorem
 | volume = 74
 | year = 2004| s2cid = 124603912
 }}.
*{{Citation
| last=Diestel
| first=Reinhard
| title=Graph Theory
| publisher=[[Springer Science+Business Media|Springer]]
| year=2005
| edition=3rd
| isbn=978-3-540-26182-7
| url=http://www.math.uni-hamburg.de/home/diestel/books/graph.theory/
| accessdate=2024-01-30
| archive-date=2011-07-28
| archive-url=https://web.archive.org/web/20110728103939/http://www.math.uni-hamburg.de/home/diestel/books/graph.theory/
| dead-url=no
}}.
*{{citation
 | last = Eppstein | first = D. | author-link = David Eppstein
 | doi = 10.1007/s004530010020
 | issue = 3–4
 | journal = [[Algorithmica]]
 | mr = 1759751
 | pages = 275–291
 | title = Diameter and treewidth in minor-closed graph families
 | volume = 27
 | year = 2000| arxiv = math/9907126| s2cid = 3172160 }}.
*{{citation
 | last1 = Feige | first1 = Uriel
 | last2 = Hajiaghayi | first2 = MohammadTaghi 
 | last3 = Lee| first3 = James R.
 | title = Improved approximation algorithms for minimum weight vertex separators
 | journal = [[SIAM Journal on Computing]]
 | volume = 38 | issue = 2 | year = 2008 | pages = 629–657 | doi = 10.1137/05064299X| citeseerx = 10.1.1.597.5634}}.
*{{citation
 | last1 = Fomin | first1 = Fedor V. | author1-link = Fedor Fomin
 | last2 = Todinca | first2 = Ioan
 | last3 = Villanger | first3 = Yngve
 | doi = 10.1137/140964801
 | issue = 1
 | journal = [[SIAM Journal on Computing]]
 | pages = 54–87
 | title = Large induced subgraphs via triangulations and CMSO
 | volume = 44
 | year = 2015| arxiv = 1309.1559
 | s2cid = 15880453 }}.
*{{citation
 | last1 = Frick | first1 = Markus
 | last2 = Grohe | first2 = Martin | author2-link = Martin Grohe
 | doi = 10.1145/504794.504798
 | issue = 6
 | journal = [[Journal of the ACM]]
 | mr = 2143836
 | pages = 1184–1206
 | title = Deciding first-order properties of locally tree-decomposable structures
 | volume = 48
 | year = 2001| arxiv = cs/0004007
 | s2cid = 999472
 }}.
*{{citation
 | last1 = Fomin| first1 = Fedor V.
 | last2 = Lokshtanov| first2 = Daniel
 | last3 = Saurabh| first3 = Saket
 | last4 = Pilipczuk| first4 = Michal
 | last5 = Wrochna| first5 = Marcin
 | title = Fully polynomial-time parameterized computations for graphs and matrices of low treewidth
 | journal = ACM Transactions on Algorithms
 | volume = 14
 | issue = 3 
 | year = 2018 
 | pages = 34:1–34:45 
 | doi = 10.1145/3186898| arxiv = 1511.01379| s2cid = 2144798
 }}.
*{{citation
 | last1 = Grigoriev | first1 = Alexander
 | last2 = Bodlaender | first2 = Hans L. | author2-link = Hans L. Bodlaender
 | doi = 10.1007/s00453-007-0010-x
 | issue = 1
 | journal = [[Algorithmica]]
 | mr = 2344391
 | pages = 1–11
 | title = Algorithms for graphs embeddable with few crossings per edge
 | volume = 49
 | year = 2007| citeseerx = 10.1.1.65.5071| s2cid = 8174422
 }}.
*{{Citation
 | title = ''S''-functions for graphs
 | year = 1976
 | last = Halin | first = Rudolf | author-link = Rudolf Halin
 | journal = Journal of Geometry
 | pages = 171–186
 | volume = 8
 | issue = 1–2
 | doi=10.1007/BF01917434
| s2cid = 120256194
 }}.
*{{citation|title=	Encyclopedia of Algorithms|editor-first=Ming-Yang|editor-last=Kao|publisher=Springer|year=2008|isbn=9780387307701|contribution=Treewidth of graphs|page=969|url=https://books.google.com/books?id=i3S9_GnHZwYC&pg=PA969|quote=Another long-standing open problem is whether there is a polynomial-time algorithm to compute the treewidth of planar graphs.}}
*{{citation
 | last = Korhonen | first = Tuukka
 | contribution = A Single-Exponential Time 2-Approximation Algorithm for Treewidth
 | doi = 10.1109/FOCS52979.2021.00026
 | pages = 184–192
 | publisher = IEEE
 | title = Proceedings of the 62nd IEEE Annual Symposium on Foundations of Computer Science
 | arxiv = 2104.07463
 | year = 2021| s2cid = 233240958
 }}.
*{{citation
 | last = Lagergren | first = Jens
 | contribution = An upper bound on the size of an obstruction
 | doi = 10.1090/conm/147/01202
 | location = Providence, RI
 | mr = 1224734
 | pages = 601–621
 | publisher = American Mathematical Society
 | series = Contemporary Mathematics
 | title = Graph structure theory (Seattle, WA, 1991)
 | volume = 147
 | year = 1993| isbn = 9780821851609
 }}.
*{{citation
 | last = Lagergren | first = Jens
 | doi = 10.1006/jagm.1996.0002
 | issue = 1
 | journal = Journal of Algorithms
 | mr = 1368716
 | pages = 20–44
 | title = Efficient parallel algorithms for graphs of bounded tree-width
 | volume = 20
 | year = 1996}}.
*{{citation
 | last = Ramachandramurthi | first = Siddharthan
 | doi = 10.1137/S0895480195280010
 | issue = 1
 | journal = [[SIAM Journal on Discrete Mathematics]]
 | mr = 1430552
 | pages = 146–157
 | title = The structure and number of obstructions to treewidth
 | volume = 10
 | year = 1997}}.
*{{citation
 | last = Reed | first = Bruce A. | author-link = Bruce Reed (mathematician)
 | editor1-last = Kosaraju | editor1-first = S. Rao
 | editor2-last = Fellows | editor2-first = Mike
 | editor3-last = Wigderson | editor3-first = Avi
 | editor4-last = Ellis | editor4-first = John A.
 | contribution = Finding approximate separators and computing tree width quickly
 | doi = 10.1145/129712.129734
 | pages = 221–228
 | publisher = ACM
 | title = Proceedings of the 24th Annual ACM Symposium on Theory of Computing, May 4-6, 1992, Victoria, British Columbia, Canada
 | year = 1992| s2cid = 16259988 | doi-access = free
 }}.
*{{citation
 | last1 = Robertson | first1 = Neil | author-link1 = Neil Robertson (mathematician)
 | last2 = Seymour | first2 = Paul D. | author-link2 = Paul Seymour (mathematician)
 | title = Graph minors III: Planar tree-width
 | journal = [[Journal of Combinatorial Theory]] | series=Series B
 | volume = 36
 | issue = 1 | year = 1984 | pages = 49–64
 | doi = 10.1016/0095-8956(84)90013-3| doi-access = free}}.
*{{citation
 | last1 = Robertson | first1 = Neil | author-link1 = Neil Robertson (mathematician)
 | last2 = Seymour | first2 = Paul D. | author-link2 = Paul Seymour (mathematician)
 | title = Graph minors V: Excluding a planar graph
 | journal = [[Journal of Combinatorial Theory]] | series=Series B
 | volume = 41 | issue = 1 | year = 1986 | pages = 92–114 | doi = 10.1016/0095-8956(86)90030-4| doi-access = free }}.
*{{citation
 | last1 = Robertson | first1 = Neil | author-link1 = Neil Robertson (mathematician)
 | last2 = Seymour | first2 = Paul D. | author-link2 = Paul Seymour (mathematician)
 | title = Graph Minors XIII: The Disjoint Paths Problem
 | journal = [[Journal of Combinatorial Theory]] | series=Series B
 | volume = 63 | issue = 1 | year = 1995 | pages = 65–110 | doi = 10.1006/jctb.1995.1006| doi-access = free }}.
*{{citation
 | last1 = Robertson | first1 = Neil | author1-link = Neil Robertson (mathematician)
 | last2 = Seymour | first2 = Paul | author2-link = Paul Seymour (mathematician)
 | last3 = Thomas | first3 = Robin | author3-link = Robin Thomas (mathematician)
 | doi = 10.1006/jctb.1994.1073
 | issue = 2
 | journal = [[Journal of Combinatorial Theory]] | series = Series B
 | mr = 1305057
 | pages = 323–348
 | title = Quickly excluding a planar graph
 | volume = 62
 | year = 1994| doi-access = free
 }}.
*{{citation
 | last1 = Satyanarayana | first1 = A.
 | last2 = Tung | first2 = L.
 | doi = 10.1002/net.3230200304
 | issue = 3
 | journal = Networks
 | mr = 1050503
 | pages = 299–322
 | title = A characterization of partial 3-trees
 | volume = 20
 | year = 1990}}.
*{{citation
 | last1 = Seymour | first1 = Paul D. | author-link1 = Paul Seymour (mathematician)
 | last2 = Thomas | first2 = Robin | author2-link=Robin Thomas (mathematician)
 | title = Graph searching and a min-max theorem for tree-width
 | journal = [[Journal of Combinatorial Theory]] | series=Series B
 | volume = 58 | issue = 1 | pages = 22–33 | doi = 10.1006/jctb.1993.1027
 | year = 1993| doi-access = free }}.
*{{citation
 | last1 = Shoikhet
 | first1 = Kirill
 | last2 = Geiger
 | first2 = Dan
 | editor1-last = Kuipers
 | editor1-first = Benjamin
 | editor2-last = Webber
 | editor2-first = Bonnie L.
 | contribution = A Practical Algorithm for Finding Optimal Triangulations
 | contribution-url = https://www.aaai.org/Library/AAAI/1997/aaai97-029.php
 | pages = 185–190
 | publisher = AAAI Press / The MIT Press
 | title = Proceedings of the Fourteenth National Conference on Artificial Intelligence and Ninth Innovative Applications of Artificial Intelligence Conference, AAAI 97, IAAI 97, July 27-31, 1997, Providence, Rhode Island, USA
 | year = 1997
 | accessdate = 2024-01-30
 | archive-date = 2022-02-02
 | archive-url = https://web.archive.org/web/20220202080309/https://www.aaai.org/Library/AAAI/1997/aaai97-029.php
 | dead-url = no
 }}.
*{{citation
 | last = Thorup | first = Mikkel | author-link = Mikkel Thorup
 | title = All structured programs have small tree width and good register allocation
 | journal = [[Information and Computation]]
 | volume = 142 | issue = 2 | year = 1998 | pages = 159–181 | doi = 10.1006/inco.1997.2697| doi-access = free }}.
*{{cite arXiv
 | last1 = Korhonen | first1 = Tuukka
 | last2 = Lokshtanov | first2 = Daniel
 | title = An Improved Parameterized Algorithm for Treewidth
 | eprint = 2211.07154
 | year = 2022
 | class = cs.DS
 | mode=cs2}}.

{{refend}}
[[Category:图论]]
[[Category:图常量]]