“径宽”的版本间的差异
跳到导航
跳到搜索
| 第1行： | 第1行： | ||
| − | [[图论]]中，[[图]] | + | [[图论]]中，[[图 (数学)|图]]''G''的'''径分解'''（path decomposition）是''G''的“加粗”[[道路 (图论)|路径图]]表示，<ref>{{harvtxt|Diestel|Kühn|2005}}.</ref>''G''的'''径宽'''（pathwidth）是衡量形成''G''的路径被加粗的程度。更正式地说，径分解是''G''的[[顶点 (图论)|顶点]][[子集]]序列，使每条边的端点出现在某一子集中，并使每个顶点都出现在子集连续子序列中，<ref name="rs83">{{harvtxt|Robertson|Seymour|1983}}.</ref>径宽等于这样的分解中最大集的大小减一。 |
| + | 径宽也叫做'''区间厚度'''（interval thickness，等于''G''的[[区间图|区间]]父图中的[[最大团]]大小减一）、'''顶点分隔数'''（vertex separation number）或'''结点搜索数'''（node searching number）。<ref>{{harvtxt|Bodlaender|1998}}.</ref> | ||
| − | 径宽与径分解同[[树宽]]、[[树分解]]关系密切，在[[图子式]] | + | 径宽与径分解同[[树宽]]、[[树分解]]关系密切，在[[图子式]]理论中起关键作用：在[[图子式]]下封闭、不含所有[[树 (图论)|森林]]的图族可描述为径宽有界，<ref name="rs83"/>子式闭图族的[[图结构定理|一般结构理论]]中出现的“涡”（vortex）的径宽也有界。<ref name="Robertson 2003">{{harvtxt|Robertson|Seymour|2003}}.</ref>径宽与径宽有界图在[[超大规模集成电路]]设计、[[绘制 (图论)|图绘制]]、[[计算语言学]]等领域也有应用。 |
| − | + | 计算任意图的径宽、甚至精确近似径宽都是[[NP困难]]的。<ref name="npc"/><ref name="bghk92">{{harvtxt|Bodlaender|Gilbert|Hafsteinsson|Kloks|1992}}.</ref>不过，这问题是[[固定参数可解]]的：测试图的径宽是否为''k''，耗时与图的大小呈线性关系，而与''k''呈上指数关系。<ref name="bounded-tw-algs"/>另外，对[[树 (图论)|树]]之类的特殊图，径宽可在多项式时间内算得，而不依赖于''k''。{{sfnp|Bodlaender|1994}}<ref name="tree-algs"/> | |
| + | 对图的径分解使用[[动态规划]]，可以将图算法中很多问题在径宽有界图上高效解决。<ref name="Arnborg 1985">{{harvtxt|Arnborg|1985}}.</ref>径分解也可测量[[树宽]]有界图上动态规划算法的[[空间复杂度]]。<ref name="apt00">{{harvtxt|Aspvall|Proskurowski|Telle|2000}}.</ref> | ||
| − | == 定义 == | + | ==定义== |
| + | [[File:Pathwidth.JPG|thumb|upright=1.35|径宽为2的例图''G''，其径分解宽度为2。图像下半部是相同的图与径分解，添加了颜色以示强调。（本例改编自{{harvp|Bodlaender|1994a}}，添加了记号）]] | ||
| + | {{harvs | last1 = Robertson | first1 = Neil | author1-link = Neil Robertson (mathematician) | last2 = Seymour | first2 = Paul | author2-link = Paul Seymour (mathematician) | year = 1983 | txt}}在[[图子式]]系列论文的第一篇中，将图''G''的径分解定义为''G''的顶点子集<math>X_i</math>序列，满足两条属性： | ||
| + | # 对''G''中每条边，存在''i''使边的两端点都属于子集<math>X_i</math>； | ||
| + | # <math>\forall i\le j\le k,\ X_i \cap X_k \subseteq X_j.</math> | ||
| + | 第二条性质等价于要求包含任意特定顶点的子集构成整个序列的连续子列。用系列论文后期的话来说，径分解是[[树分解]]<math>(X,\ T)</math>，其中分解的底树''T''是路径图。 | ||
| + | 径分解的宽度与树分解类似，是<math>{\rm max}_i|X_i|-1</math>，''G''的径宽是''G''的径分解的最小宽度。在径宽的大多数应用中，<math>X_i</math>的大小减不减一没什么差别，主要是为了使路径图的径宽等于1。 | ||
| + | |||
| + | ==其他特征== | ||
| + | 如{{harvtxt|Bodlaender|1998}}所描述的，径宽可用许多等价方法表征。 | ||
| + | |||
| + | ===粘合序列=== | ||
| + | 径分解可表述为图<math>G_i</math>的序列，找到来自序列中连续图的顶点对，并将图粘合在一起，所有粘合的结果就是''G''。在径分解的第一个定义中，图<math>G_i</math>可看作是集合<math>X_i</math>的[[诱导子图]]，连续（successive）诱导子图中的两顶点被''G''中相同顶点诱导时，就会被粘在一起；反之，可以把集合<math>X_i</math>恢复为图<math>G_i</math>的顶点集。则径分解的宽度比某一图<math>G_i</math>的最大顶点数少1。<ref name="rs83"/> | ||
| + | |||
| + | ===区间厚度=== | ||
| + | [[File:Interval graph.svg|thumb|upright=1.25|径宽为2的[[区间图]]，而4个最大团ABC、ACD、CDE、CDF的大小为3。]] | ||
| + | 任意图''G''的径宽等于含''G''（以''G''为子图）的[[区间图]]的最小团数减一。<ref>{{harvtxt|Bodlaender|1998}}, Theorem 29, p. 13.</ref>即，对''G''的每种径分解，都能找到''G''的区间子图；对''G''的每个区间父图，都能找到''G''的径分解，使分解的宽度比区间图团数小1。 | ||
| + | |||
| + | 假设给出了''G''的径分解。则可将分解的结点表为直线上的点（按路径顺序），并将每个顶点''v''表示为以这些点为端点的闭区间。这样，包含''v''的径分解结点就对应''v''在区间中的代表点。''G''顶点形成的区间[[导出子图|交图]]是包含''G''的区间图，其最大团由包含代表点的区间集给出，大小比''G''的径宽大1。 | ||
| + | |||
| + | 设''G''是某区间图的子图，团数<math>p+1</math>，则''G''有宽''p''的径分解，其结点由区间图的[[最大团]]给出。例如，图中的区间图及其区间表示的径分解有5个结点，分别对应5个最大团ABC、ACD、CDE、CDF、FG；最大团大小为3，这径分解的宽度为2。 | ||
| + | 径宽与区间厚度之间的等价关系同树宽与[[弦图]]（给定图是弦图的子图）的最小团数（减一）的等价关系非常相似。区间图是弦图的特例，弦图可表为共同树的子树的交图，这类似于区间图是路径子径的交图。 | ||
| + | |||
| + | ===顶点分隔数=== | ||
| + | 设图''G''的顶点是[[全序关系|线性有序]]的。则，''G''的顶点分隔数是满足下列条件的最小数''s''：对顶点''v''，最多''s''个顶点在排序中先于''v''，但有''v''或更靠后的顶点相邻。 | ||
| + | ''G''的顶点分隔数是''G''的任意线性排序的最小顶点分隔数。顶点分隔数由{{harvtxt|Ellis|Sudborough|Turner|1983}}定义，等于''G''的径宽。<ref>{{harvtxt|Kinnersley|1992}}; {{harvtxt|Bodlaender|1998}}, Theorem 51.</ref> | ||
| + | 这源于前述的与区间图团数的等价关系：若''G''是区间图''I''的子图，并以所有区间端点都分离的方式表示（如图所示），则''I''的区间左端点排序的顶点分隔数比''I''的团数小1。反过来，从''G''的线性排序可推导出一种区间表示：顶点''v''的区间左端点是其在排序中的位置，右端点是''v''在排序中最后一个邻居的位置。 | ||
| + | |||
| + | ===结点搜索数=== | ||
| + | 图上的结点搜索策略是[[追逃对策]]的一种形式，当中一组搜索者合作追踪藏在图中的逃犯。搜索者被置于图的顶点上，逃犯可能在任意边上，位置与移动对搜索者不可见。每个回合中，搜索者的部分或全部可从顶点移动到另一顶点（任意移动，不必沿边），逃犯可以沿不经过搜索者顶点的任意路径移动。逃犯所在边的两端点都被搜索者占据时，就被抓获。图的结点搜索数是必然能抓到逃犯的最少搜索者数。如{{harvtxt|Kirousis|Papadimitriou|1985}}所示，图的结点搜索数等于其区间厚度。搜索者的最优策略是不断移动搜索者，使他们在连续回合中形成具有最小顶点分隔数的线性排序的分隔集。 | ||
| + | |||
| + | ==界== | ||
| + | [[File:Caterpillar tree.svg|thumb|[[毛虫树]]，径宽为1的最大图。]] | ||
| + | 径宽为''k''的''n''顶点图至多有<math>k(n-k+\frac{k-1}{2})</math>条边，是最大''k''径宽图（即径宽为''k''、无论怎样添加边都必改变径宽的图）的边数。径宽为''k''的最大图要么是''k''径图要么是''k''毛虫图，它们是两种特殊的''k''树。''k''树是恰有<math>n-k</math>个[[最大团]]（含<math>k+1</math>个顶点）的[[弦图]]；在本身不是<math>(k+1)</math>团的''k''树中，每个最大团要么将图分隔成多个部分，要么包含单个叶顶点（只属于一个最大团的顶点）。''k''径图是至少有两叶的''k''树，''k''毛虫图是可分割维''k''径与一组''k''叶的''k''树，其中每片叶还与''k''径中的独立''k''团相邻。径宽为1的最大图是[[毛虫树]]。<ref>{{harvtxt|Proskurowski|Telle|1999}}.</ref> | ||
| + | |||
| + | 由于径分解是树分解的特例，径宽不小于[[树宽]]，且不大于[[割宽]]，即在图顶点的最优线性排列中，前后顶点组之间割边的最小数。这是因为，顶点分隔数即前后顶点组的邻接数不大于割边数。<ref>{{harvtxt|Korach|Solel|1993}}, Lemma 3 p.99; {{harvtxt|Bodlaender|1998}}, Theorem 47, p. 24.</ref>出于类似原因，割宽不大于径宽乘顶点的[[度 (图论)|最大度]]。<ref>{{harvtxt|Korach|Solel|1993}}, Lemma 1, p. 99; {{harvtxt|Bodlaender|1998}}, Theorem 49, p. 24.</ref> | ||
| + | |||
| + | 任意''n''顶点[[树 (图论)|森林]]都有径宽<math>O(\log n)</math>。<ref>{{harvtxt|Korach|Solel|1993}}, Theorem 5, p. 99; {{harvtxt|Bodlaender|1998}}, Theorem 66, p. 30. {{harvtxt|Scheffler|1992}}为''n''顶点森林的径宽提供了更紧的上界：<math>\log_3(2n+1)</math>。</ref>例如，对一个森林，总能找到恒定多的顶点，使得去掉它们后形成至多有<math>\frac{2n}{3}</math>个顶点的两片子森林。如此递归地分隔子森林，将分隔顶点置于两者之间，形成的线性排列具有对数顶点搜索数。此技术用于树分解时，可知，若''n''顶点图''G''的树宽为''t''，则''G''的径宽是<math>O(t\log n)</math>。<ref>{{harvtxt|Korach|Solel|1993}}, Theorem 6, p. 100; {{harvtxt|Bodlaender|1998}}, Corollary 24, p.10.</ref>由于[[外平面图]]、[[系列并行图]]、[[哈林图]]的树宽都有界，它们的径宽最多为对数的。 | ||
| + | |||
| + | 此外，径宽还通过[[线图]]，同[[团宽]]与[[割宽]]有关系。''G''的边在其线图<math>L(G)</math>中都有对应的顶点，当''G''中相应的两边有共同端点时，<math>L(G)</math>中的两顶点就是相邻的。当且仅当图族的线图的线性团宽（用邻接1个新顶点的操作取代了团宽的不交并操作）有界，图族的径宽有界。<ref>{{harvtxt|Gurski|Wanke|2007}}.</ref>若某3及以上个顶点的连通图的最大度为3，则其割宽等于线图的顶点分隔数。<ref>{{harvtxt|Golovach|1993}}.</ref> | ||
| + | |||
| + | [[平面图]]的径宽最多与顶点数的平方根成正比。<ref>{{harvtxt|Bodlaender|1998}}, Corollary 23, p. 10.</ref>找到具有这种宽度的径分解，一种方法是（与上述森林的对数宽径分解类似）用[[平面分隔定理]]找到<math>O(\sqrt n)</math>个顶点的集合，其将图分隔为至多有<math>\frac{2n}{3}</math>个顶点的两个子图，如此递归地分隔子图，最后将两子图的递归径分解连接起来。同样的技术也适用于类似分离器定理成立的任何一类图。<ref>{{harvtxt|Bodlaender|1998}}, Theorem 20, p. 9.</ref>与平面图一样，任何固定的子式闭图族中的图都有大小为<math>O(\sqrt n)</math>的分隔子，<ref>{{harvtxt|Alon|Seymour|Thomas|1990}}.</ref>因此此类图族中图的径宽也是<math>O(\sqrt n)</math>。对某类平面图，图的径宽与其[[对偶图]]的径宽必须在一常数因子范围内，对于双连通外平面图<ref>{{harvtxt|Bodlaender|Fomin|2002}}; {{harvtxt|Coudert|Huc|Sereni|2007}}.</ref>与多面体图<ref>{{harvtxt|Fomin|Thilikos|2007}}; {{harvtxt|Amini|Huc|Pérennes|2009}}.</ref>，这种形式的边界是已知的。2连通平面图的对偶图的径宽小于线图的径宽。<ref>{{harvtxt|Fomin|2003}}.</ref>至于在其他情形下，平面图径宽与对偶图径宽是否总相差某常数因子，仍是未知的。 | ||
| + | |||
| + | 在某些类的图中，径宽与树宽总相等。已证明的有[[余图]]、<ref name="bm90">{{harvtxt|Bodlaender|Möhring|1990}}.</ref>[[置换图]]、<ref name="bkk93">{{harvtxt|Bodlaender|Kloks|Kratsch|1993}}.</ref>[[可比图]]之[[补图|补]]、<ref name="hm94">{{harvtxt|Habib|Möhring|1994}}.</ref>[[区间序]]的可比图。<ref name="g95">{{harvtxt|Garbe|1995}}.</ref> | ||
| + | |||
| + | {{unsolved|数学|''n''顶点[[立方图]]的径宽上界是多少？}} | ||
| + | 在[[立方图]]中，或更广义地在任何最大顶点度为3的图中，径宽不大于<math>\frac{n}{6}+o(n)</math>，其中''n''是顶点数。存在径宽为<math>0.082n</math>的立方图，但如何缩小这下界与上界<math>\frac{n}{6}</math>之间的差距，目前还不得而知。<ref name="fh06">{{harvtxt|Fomin|Høie|2006}}.</ref> | ||
| + | |||
| + | ==计算径分解== | ||
| + | 确定给定图的径宽是否大于''k''的问题是[[NP完全]]的（''k''也是输入）。<ref name="npc">{{harvtxt|Kashiwabara|Fujisawa|1979}}; {{harvtxt|Ohtsuki|Mori|Kuh|Kashiwabara|1979}}; {{harvtxt|Lengauer|1981}}; {{harvtxt|Arnborg|Corneil|Proskurowski|1987}}.</ref>计算任意''n''顶点图径宽的最坏情形的最优时间边界为<math>O(2^nn^c)</math>，''c''是常数。<ref>{{harvtxt|Fomin|Kratsch|Todinca|Villanger|2008}}.</ref>不过，已经有几种算法可在径宽较小、输入图类别有限或近似的情形下更高效地计算径分解。 | ||
| + | |||
| + | ===固定参数可解=== | ||
| + | 径宽是[[固定参数可解]]的：对任意常数''k''，都可测试径宽是否大于''k''，若不大于''k''，则在线性时间内找到宽''k''的径分解。<ref name="bounded-tw-algs"/>一般来说，这类算法分两阶段运行。第一阶段，假设图的径宽为''k''，以找到并非最优的径分解或树分解，宽度可作为''k''的函数而变为约束。第二阶段，对这分解运用[[动态规划]]算法，以找到最优分解。然而，已知的这类算法的时间界限是<math>k^2</math>的指数级，除了最小的''k''外，都是不切实际的。<ref>{{harvtxt|Downey|Fellows|1999}}, p.12.</ref>对于<math>k=2</math>的情形，{{harvtxt|de Fluiter|1997}}给出了基于2径宽图的结构分解的精确限行时间算法。 | ||
| + | |||
| + | ===特殊图类=== | ||
| + | {{harvp|Bodlaender|1994}}调查了计算各种特殊图类的径宽的复杂性。若图''G''是有界度图、<ref name="ms88">{{harvtxt|Monien|Sudborough|1988}}.</ref>[[平面图]]、<ref name="ms88"/>有界度平面图、<ref name="ms88"/>[[弦图]]、<ref>{{harvtxt|Gustedt|1993}}.</ref>弦多米诺、<ref>{{harvtxt|Kloks|Kratsch|Müller|1995}}. 弦多米诺是顶点都属于至多2个最大团的弦图。</ref>[[可比图]]之[[补图|补]]、<ref name="hm94"/>[[二分图|二分]][[距离遗传图]]<ref name="kbmk">{{harvtxt|Kloks|Bodlaender|Müller|Kratsch|1993}}.</ref>，确定图''G''的径宽是否最大是''k''的问题仍是NP完全的。对于包含二分距离遗传图的图族（二分图、弦二分图、距离遗传图、[[循环图]]之类），也是NP完全的。<ref name="kbmk"/> | ||
| + | |||
| + | 不过，对于树与森林，径宽可在线性时间内算得。<ref name="tree-algs">{{harvtxt|Möhring|1990}}; {{harvtxt|Scheffler|1990}}; {{harvtxt|Ellis|Sudborough|Turner|1994}}; {{harvtxt|Peng|Ho|Hsu|Ko|1998}}; {{harvtxt|Skodinis|2000}}; {{harvtxt|Skodinis|2003}}; {{harvtxt|Coudert|Huc|Mazauric|2012}}.</ref>对树宽有界图族（[[系列并行图]]、[[外平面图]]、[[哈林图]]）<ref name="bounded-tw-algs">{{harvtxt|Bodlaender|1996}}; {{harvtxt|Bodlaender|Kloks|1996}}</ref>、[[裂图]]<ref>{{harvtxt|Kloks|Bodlaender|1992}}; {{harvtxt|Gustedt|1993}}.</ref>、弦图之补<ref>{{harvtxt|Garbe|1995}}将此成果归功于Ton Kloks的博士论文（1993）；Garbe对区间序的可比图的多项式时间算法推广了结果，而弦图属于此类可比图。</ref>、[[置换图]]<ref name="bkk93"/>、[[余图]]<ref name="bm90"/>、[[圆弧图]]<ref>{{harvtxt|Suchan|Todinca|2007}}.</ref>、区间序的可比图<ref name="g95"/>、[[区间图]]，也可在多项式时间内计算出来。这种情形下，径宽比覆盖图的区间表示中所有点的最大区间数小1。 | ||
| + | |||
| + | ===近似算法=== | ||
| + | 将图的径宽近似到加常数范围内，是NP难的。<ref name="bghk92"/> | ||
| + | 已知[[近似率]]最佳的多项式时间近似算法是<math>O((\log n)^{3/2})</math>。<ref>{{harvtxt|Feige|Hajiaghayi|Lee|2005}}.</ref> | ||
| + | 关于计算径宽的早期近似算法，见{{harvtxt|Bodlaender|Gilbert|Hafsteinsson|Kloks|1992}}与{{harvtxt|Guha|2000}}；关于受限图类的近似计算，见{{harvtxt|Kloks|Bodlaender|1992}}。 | ||
| + | |||
| + | ==图子式== | ||
| + | 图''G''的[[图子式|子式]]是由''G''通过收缩边、移除边、移除顶点得到的另一张图。图子式有深奥的理论，其中几个重要结果涉及径宽。 | ||
| + | |||
| + | ===排除森林=== | ||
| + | 若图族''F''对取子式封闭（即''F''成员的子式还在''F''中），则由[[罗伯森–西摩定理]]，''F''的特征是在禁子式有限集''X''中没有任何子式。<ref name="gm20">{{harvtxt|Robertson|Seymour|2004}}.</ref>例如，[[瓦格纳定理]]指出，[[平面图]]是既没有[[完整图]]<math>K_5</math>也没有[[完全二分图]]<math>K_{3,\ 3}</math>作为子式的图。很多时候，''F''的性质与''X''的性质密切相关，此类的第一个结果由{{harvtxt|Robertson|Seymour|1983}}提出，<ref name="rs83"/>将有界径宽与禁子式族中[[树 (图论)|森林]]的存在联系起来。具体来说，若存在常数''p''使''F''中图的径宽不大于''p''，则称图族''F''具有有界径宽。那么，当且仅当''F''的禁子式集''X''至少包括一个森林时，子式闭族''F''具有有界的径宽。 | ||
| + | |||
| + | 从一个方向来看，这结果很容易证明：若''X''不含森林，则“无''X''子式图”的径宽便无界。因为这时，无''X''子式图将包含所有森林，特别是包括[[二叉树#完美二叉树|完美二叉树]]。而一棵<math>2k+1</math>层的完美二叉树的径宽为''k''，所以这时无''X''子式图的径宽无解。从另一方向看，若''X''包含''n''顶点森林，则无''X''子式图的径宽不大于<math>n-2</math>。<ref>{{harvtxt|Bienstock|Robertson|Seymour|Thomas|1991}}; {{harvtxt|Diestel|1995}}; {{harvtxt|Cattell|Dinneen|Fellows|1996}}.</ref> | ||
| + | ===径宽有界的障碍=== | ||
| + | [[File:Pathwidth-1 obstructions.svg|thumb|径宽为1的图的禁子式。]] | ||
| + | 径宽不大于''p''的性质本身对取子式封闭：若''G''的径分解宽度不大于''p''，则从''G''中删去任何边，同一径分解仍有效，且可以从''G''及其径分解中删去任意顶点而不增加宽度。同样，通过合并表示收缩后边的两端点的子径，也可在收缩边时不增加分解宽度。因此，径宽至多为''p''的图可用排除子式的集合<math>X_p</math>描述。<ref name="gm20"/><ref name="obstructions">{{harvtxt|Kinnersley|1992}}; {{harvtxt|Takahashi|Ueno|Kajitani|1994}}; {{harvtxt|Bodlaender|1998}}, p. 8.</ref> | ||
| + | |||
| + | 虽然<math>X_p</math>必然包括森林，但并不是说<math>X_p</math>中的所有图都是森林：例如，<math>X_1</math>包含2张图，一个7顶点树与三角<math>K_3</math>。而<math>X_p</math>中的树集可以精确描述：它们是<math>X_{p-1}</math>中三棵树通过边，连接新的根顶点与3棵小树中任意顶点而形成的树。例如，<math>X_1</math>中的7顶点树就是这样由<math>X_0</math>中的2顶点树（一条边）组成的。基于这种构造，可以证明<math>X_p</math>中的禁子式数至少为<math>(p!)^2</math>。<ref name="obstructions"/>已计算出2径宽图的完备禁子式集<math>X_2</math>，其中包含110个图。<ref>{{harvtxt|Kinnersley|Langston|1994}}.</ref> | ||
| + | |||
| + | ===结构理论=== | ||
| + | 子式闭图族的[[图结构定理]]指出，对任意图族''F''，其中的图可分解为能[[图嵌入|嵌入]]到[[亏格]]有界曲面上的图的[[团和]]，且团和的每个分量都有有界多的顶点（apex）与涡（vortex）。这里的顶点可能与其组分中任何顶点相邻，涡是径宽有界图，粘合到某组分的亏格有界嵌入的面上。涡所嵌入面周围的顶点的循环排序必须与涡的径分解相容，即，打破循环、形成线性排序必然产生顶点分隔数有界的排序。<ref name="Robertson 2003"/>这一理论中，径宽与任意子式闭图族密切相关，具有重要的算法应用。<ref>{{harvtxt|Demaine|Hajiaghayi|Kawarabayashi|2005}}.</ref> | ||
| + | |||
| + | ==应用== | ||
| + | ===超大规模集成电路=== | ||
| + | [[超大规模集成电路]]设计中，顶点分隔问题最初是将电路分为子系统的方法，子系统边界有少量元件。<ref name="ms88"/> | ||
| + | |||
| + | {{harvtxt|Ohtsuki|Mori|Kuh|Kashiwabara|1979}}使用区间厚度模拟VLSI一维布局所需的轨道数，此布局由网络系统相互连接的模块组成。在他们的模型中，顶点代表网，若两网都连接到同一模块，就将两顶点由边相连；也就是说，若将模块与网视作[[超图]]的结点与超边，则由它们形成的图就是超图的[[线图]]。这超图的区间表示与[[图着色问题|着色]]描述了沿水平轨道（一种颜色对应一条轨道）系统的网的排列，使模块可沿轨道以线性顺序排列，并连接到相应的网。区间图都是[[完美图]]<ref>{{harvtxt|Berge|1967}}.</ref>，表明这类最佳排列中，所需颜色数等于网图的区间完备化的团数。 | ||
| + | |||
| + | 门矩阵布局<ref>{{harvtxt|Lopez|Law|1980}}.</ref>是一种用于[[布尔逻辑]]电路的[[CMOS]] VLSI布局。当中，信号沿“线”（垂直线段）传播，而电路的每个门则由沿水平线段的一系列器件特征构成。因此，代表门的水平线段须与代表门输入输出的线路的垂直线段交叉。与{{harvtxt|Ohtsuki|Mori|Kuh|Kashiwabara|1979}}的布局类似，通过计算以线路为顶点，以共享同一门的线对为边的图的径宽，可以找到使排列线路的垂直轨道数最小的布局。<ref name="fl89">{{harvtxt|Fellows|Langston|1989}}.</ref>这种算法方法也可为[[可编程逻辑阵列]]的折叠问题建模。<ref>{{harvtxt|Möhring|1990}}; {{harvtxt|Ferreira|Song|1992}}.</ref> | ||
| + | |||
| + | ===图绘制=== | ||
| + | 径宽在[[绘制 (图论)|图绘制]]中有多个应用： | ||
| + | * 给定[[交叉数]]的最小图的径宽受交叉数函数的约束。<ref name="h03">{{harvtxt|Hliněny|2003}}.</ref> | ||
| + | * 树的顶点可画在多少条平行线上而边不交（根据对相邻顶点在线序列上摆放方式的各种自然限制），与树的径宽成正比。<ref>{{harvtxt|Suderman|2004}}.</ref> | ||
| + | * 图''G''的''k''交叉''h''层绘图是将''G''的顶点放置在''h''条水平线上，边在其间以单调多边形路径排列，使得最多有''k''处交叉。具有这种绘制的图的径宽由''h''与''k''的函数约束。于是，''h''、''k''为常值时，可在线性时间内确定图是都具有''k''交叉''h''层绘制。<ref name="dfkl08">{{harvtxt|Dujmović|Fellows|Kitching|Liotta|2008}}.</ref> | ||
| + | * ''n''顶点、径宽为''p''的图可嵌入3维格<math>p\times p\times n</math>，使得边（表为格点间的直线段）不交。于是，径宽有界图具有此种线性体积嵌入。<ref>{{harvtxt|Dujmović|Morin|Wood|2003}}.</ref> | ||
| + | |||
| + | ===编译器设计=== | ||
| + | [[高级语言]]的[[编译]]过程中，径宽见于重排直线代码序列（即无[[控制流]]分支或循环的代码）问题，使代码算得的所有值都可[[寄存器配置|放在寄存器中]]，而不必溢出到主内存中。这种应用中，我们将待编译代码表为[[有向无环图]]，其中结点是代码的输入输出值。这个DAG中，结点''x''到结点''y''的边表示''x''值是操作了''y''的输入之一。此DAG的顶点的[[拓扑排序]]表示代码的有效重排，在给定排序中评估代码所需的寄存器数由排序的顶点分隔数给出。<ref name="bgt98">{{harvtxt|Bodlaender|Gustedt|Telle|1998}}.</ref> | ||
| + | |||
| + | 对表示寄存器数的任意定值''w''，可在限行时间内确定一段直线代码能否重排，以便用不多于''w''个寄存器求值。若拓扑排序的顶点分隔数最多为''w''，则所有排序中的最小顶点分隔也不会更大，于是忽略DAG方向形成的无向图的径宽不大于''w''。可用已知的固定参数可解算法计算径宽，若是，则可在假设''w''为常数的线性时间内找到无向图的径分解。找到径分解，就可用动态规划，在线性时间内找到宽''w''的拓扑排序。<ref name="bgt98"/> | ||
| + | |||
| + | ===语言学=== | ||
| + | {{harvtxt|Kornai|Tuza|1992}}描述了径宽在[[自然语言处理]]中的应用。句子被建模为图，顶点表示词，边表示词之间的关系。例如，若形容词修饰了名词，则图中这两个词之间就会有一条边。Kornai和Tuza认为，由于人类的短时记忆能力有限，<ref>{{harvtxt|Miller|1956}}.</ref>这种图的径宽一定有界（更具体地说，他们认为是6），否则人类将无法正确解析语言。 | ||
| + | |||
| + | ===指数算法=== | ||
| + | 图算法中的很多问题都可通过对径分解进行[[动态规划]]，在径宽较小的图上高效解决。<ref name="Arnborg 1985"/>例如，若给定''n''顶点图''G''的顶点的线性排序，就有可能在<math>O(2^wn)</math>的时间内找到''G''的最大独立集。<ref name="fh06"/>在径宽有界图上，这种方法会产生以径宽为参数的固定参数可解算法。<ref name="fl89"/>这种结果在文献中不常见，因为已经包含在以树宽为参数的类似算法；然而，即使在基于树宽的动态规划算法中，径宽也会出现衡量算法[[空间复杂度]]的过程中。<ref name="apt00"/> | ||
| + | |||
| + | 同样的动态规划方法也可用于径宽无界图，产生以[[时间复杂度#指数时间|指数时间]]解决无参图问题的算法。例如，将这种方法与[[立方图]]径宽为<math>\frac{n}{6}+o(n)</math>的事实相结合，可以发现在立方图中，最大[[支配集]]的构造耗时<math>O(2^{\frac{n}{6}+o(n)})</math>，比以往方法更快。<ref name="fh06"/>类似方法还可改进立方图中[[最大割]]与最小支配集问题的指数时间算法，<ref name="fh06"/>及其他一些NP难优化问题的指数时间算法。<ref>{{harvtxt|Kneis|Mölle|Richter|Rossmanith|2005}}; {{harvtxt|Björklund|Husfeldt|2008}}.</ref> | ||
| + | |||
| + | ==注释== | ||
| + | {{reflist|30em}} | ||
| + | |||
| + | ==参考文献== | ||
| + | {{refbegin|30em}} | ||
| + | *{{citation | ||
| + | | last1 = Alon | first1 = Noga | author1-link = Noga Alon | ||
| + | | last2 = Seymour | first2 = Paul | author2-link = Paul Seymour (mathematician) | ||
| + | | last3 = Thomas | first3 = Robin | author3-link = Robin Thomas (mathematician) | ||
| + | | contribution = A separator theorem for graphs with an excluded minor and its applications | ||
| + | | doi = 10.1145/100216.100254 | ||
| + | | pages = 293–299 | ||
| + | | title = Proc. 22nd ACM Symp. on Theory of Computing (STOC 1990) | ||
| + | | year = 1990| isbn = 0897913612 | s2cid = 17521329 | doi-access = free}}. | ||
| + | *{{citation | ||
| + | | last1 = Amini | first1 = Omid | ||
| + | | last2 = Huc | first2 = Florian | ||
| + | | last3 = Pérennes | first3 = Stéphane | ||
| + | | doi = 10.1137/060670146 | ||
| + | | issue = 3 | ||
| + | | journal = [[SIAM Journal on Discrete Mathematics]] | ||
| + | | pages = 1311–1316 | ||
| + | | title = On the path-width of planar graphs | ||
| + | | volume = 23 | ||
| + | | year = 2009}}. | ||
| + | *{{citation | ||
| + | | last = Arnborg | first = Stefan | ||
| + | | doi = 10.1007/BF01934985 | ||
| + | | issue = 1 | ||
| + | | journal = BIT | ||
| + | | pages = 2–23 | ||
| + | | title = Efficient algorithms for combinatorial problems on graphs with bounded decomposability – A survey | ||
| + | | volume = 25 | ||
| + | | year = 1985| s2cid = 122263659 | ||
| + | }}. | ||
| + | *{{citation | ||
| + | | last1 = Arnborg | first1 = Stefan | ||
| + | | last2 = Corneil | first2 = Derek G. | author2-link = Derek Corneil | ||
| + | | last3 = Proskurowski | first3 = Andrzej | ||
| + | | doi = 10.1137/0608024 | ||
| + | | issue = 2 | ||
| + | | journal = SIAM Journal on Algebraic and Discrete Methods | ||
| + | | pages = 277–284 | ||
| + | | title = Complexity of finding embeddings in a {{mvar|k}}-tree | ||
| + | | volume = 8 | ||
| + | | year = 1987}}. | ||
| + | *{{citation | ||
| + | | last1 = Aspvall | first1 = Bengt | ||
| + | | last2 = Proskurowski | first2 = Andrzej | ||
| + | | last3 = Telle | first3 = Jan Arne | ||
| + | | doi = 10.1007/s004530010025 | ||
| + | | journal = [[Algorithmica]] | ||
| + | | pages = 382–394 | ||
| + | | title = Memory requirements for table computations in partial ''k''-tree algorithms | ||
| + | | volume = 27 | ||
| + | | year = 2000 | ||
| + | | issue = 3| s2cid = 9690525 | ||
| + | }}. | ||
| + | *{{citation | ||
| + | | last = Berge | first = Claude | author-link = Claude Berge | ||
| + | | contribution = Some classes of perfect graphs | ||
| + | | location = New York | ||
| + | | pages = 155–165 | ||
| + | | publisher = Academic Press | ||
| + | | title = Graph Theory and Theoretical Physics | ||
| + | | year = 1967}}. | ||
| + | *{{citation | ||
| + | | last1 = Bienstock | first1 = Dan | ||
| + | | last2 = Robertson | first2 = Neil | author2-link = Neil Robertson (mathematician) | ||
| + | | last3 = Seymour | first3 = Paul | author3-link = Paul Seymour (mathematician) | ||
| + | | last4 = Thomas | first4 = Robin | author4-link = Robin Thomas (mathematician) | ||
| + | | doi = 10.1016/0095-8956(91)90068-U | ||
| + | | issue = 2 | ||
| + | | journal = [[Journal of Combinatorial Theory|Journal of Combinatorial Theory, Series B]] | ||
| + | | pages = 274–283 | ||
| + | | title = Quickly excluding a forest | ||
| + | | volume = 52 | ||
| + | | year = 1991| doi-access = free | ||
| + | }}. | ||
| + | *{{citation | ||
| + | | last1 = Björklund | first1 = Andreas | ||
| + | | last2 = Husfeldt | first2 = Thore | ||
| + | | doi = 10.1007/s00453-007-9149-8 | ||
| + | | issue = 2 | ||
| + | | journal = [[Algorithmica]] | ||
| + | | pages = 226–249 | ||
| + | | title = Exact algorithms for exact satisfiability and number of perfect matchings | ||
| + | | volume = 52 | ||
| + | | year = 2008| s2cid = 37693881 | ||
| + | }}. | ||
| + | *{{citation | ||
| + | | last = Bodlaender | first = Hans L. | author-link = Hans L. Bodlaender | ||
| + | | contribution = A tourist guide through treewidth | ||
| + | | editor1-last = Dassow | editor1-first = Jürgen | ||
| + | | editor2-last = Kelemenová | editor2-first = Alisa | ||
| + | | pages = 1–20 | ||
| + | | publisher = Gordon and Breach | ||
| + | | series = Topics in Computer Mathematics | ||
| + | | title = Developments in Theoretical Computer Science (Proc. 7th International Meeting of Young Computer Scientists, Smolenice, 16–20 November 1992) | ||
| + | | volume = 6 | ||
| + | | year = 1994}}. | ||
| + | *{{Cite journal|last=Bodlaender|first=Hans L.|title=A tourist guide through treewidth|date=1994a |journal=Acta Cybernetica |volume=11 |pages=1–2}} | ||
| + | *{{citation | ||
| + | | last = Bodlaender | first = Hans L. | author-link = Hans L. Bodlaender | ||
| + | | doi = 10.1137/S0097539793251219 | ||
| + | | issue = 6 | ||
| + | | journal = [[SIAM Journal on Computing]] | ||
| + | | pages = 1305–1317 | ||
| + | | title = A linear-time algorithm for finding tree-decompositions of small treewidth | ||
| + | | volume = 25 | ||
| + | | year = 1996| hdl = 1874/16670 | hdl-access = free | ||
| + | }}. | ||
| + | *{{citation | ||
| + | | last = Bodlaender | first = Hans L. | author-link = Hans L. Bodlaender | ||
| + | | doi = 10.1016/S0304-3975(97)00228-4 | ||
| + | | issue = 1–2 | ||
| + | | journal = [[Theoretical Computer Science (journal)|Theoretical Computer Science]] | ||
| + | | pages = 1–45 | ||
| + | | title = A partial ''k''-arboretum of graphs with bounded treewidth | ||
| + | | volume = 209 | ||
| + | | year = 1998| doi-access = free | ||
| + | }}. | ||
| + | *{{citation | ||
| + | | last1 = Bodlaender | first1 = Hans L. | author1-link = Hans L. Bodlaender | ||
| + | | last2 = Fomin | first2 = Fedor V. | ||
| + | | doi = 10.1016/S0196-6774(02)00001-9 | ||
| + | | issue = 2 | ||
| + | | journal = Journal of Algorithms | ||
| + | | pages = 190–200 | ||
| + | | title = Approximation of pathwidth of outerplanar graphs | ||
| + | | volume = 43 | ||
| + | | year = 2002}}. | ||
| + | *{{citation | ||
| + | | last1 = Bodlaender | first1 = Hans L. | author1-link = Hans L. Bodlaender | ||
| + | | last2 = Gilbert | first2 = John R. | ||
| + | | last3 = Hafsteinsson | first3 = Hjálmtýr | ||
| + | | last4 = Kloks | first4 = Ton | ||
| + | | contribution = Approximating treewidth, pathwidth, and minimum elimination tree height | ||
| + | | doi = 10.1007/3-540-55121-2_1 | ||
| + | | pages = 1–12 | ||
| + | | series = [[Lecture Notes in Computer Science]] | ||
| + | | title = Graph-Theoretic Concepts in Computer Science | ||
| + | | volume = 570 | ||
| + | | year = 1992| isbn = 978-3-540-55121-8 | hdl = 1874/17927 | hdl-access = free | ||
| + | }}. | ||
| + | *{{citation | ||
| + | | last1 = Bodlaender | ||
| + | | first1 = Hans L. | ||
| + | | author1-link = Hans L. Bodlaender | ||
| + | | last2 = Gustedt | ||
| + | | first2 = Jens | ||
| + | | last3 = Telle | ||
| + | | first3 = Jan Arne | ||
| + | | contribution = Linear-time register allocation for a fixed number of registers | ||
| + | | pages = 574–583 | ||
| + | | title = Proc. 9th ACM–SIAM Symposium on Discrete Algorithms (SODA '98) | ||
| + | | url = http://www.ii.uib.no/~telle/bib/BGT.pdf | ||
| + | | year = 1998 | ||
| + | | accessdate = 2024-01-31 | ||
| + | | archive-date = 2023-01-30 | ||
| + | | archive-url = https://web.archive.org/web/20230130191917/https://www.ii.uib.no/~telle/bib/BGT.pdf | ||
| + | | dead-url = no | ||
| + | }}. | ||
| + | *{{citation | ||
| + | | last1 = Bodlaender | first1 = Hans L. | author1-link = Hans L. Bodlaender | ||
| + | | last2 = Kloks | first2 = Ton | ||
| + | | doi = 10.1006/jagm.1996.0049 | ||
| + | | issue = 2 | ||
| + | | journal = Journal of Algorithms | ||
| + | | pages = 358–402 | ||
| + | | title = Efficient and constructive algorithms for the pathwidth and treewidth of graphs | ||
| + | | volume = 21 | ||
| + | | year = 1996| hdl = 1874/16538 | hdl-access = free | ||
| + | }}. | ||
| + | *{{citation | ||
| + | | last1 = Bodlaender | first1 = Hans L. | author1-link = Hans L. Bodlaender | ||
| + | | last2 = Kloks | first2 = Ton | ||
| + | | last3 = Kratsch | first3 = Dieter | ||
| + | | contribution = Treewidth and pathwidth of permutation graphs | ||
| + | | doi = 10.1007/3-540-56939-1_66 | ||
| + | | pages = 114–125 | ||
| + | | publisher = Springer-Verlag | ||
| + | | series = Lecture Notes in Computer Science | ||
| + | | title = Proc. 20th International Colloquium on Automata, Languages and Programming (ICALP 1993) | ||
| + | | volume = 700 | ||
| + | | year = 1993| isbn = 978-3-540-56939-8 | title-link = International Colloquium on Automata, Languages and Programming | hdl = 1874/16657 | hdl-access = free | ||
| + | }}. | ||
| + | *{{citation | ||
| + | | last1 = Bodlaender | first1 = Hans L. | author1-link = Hans L. Bodlaender | ||
| + | | last2 = Möhring | first2 = Rolf H. | ||
| + | | contribution = The pathwidth and treewidth of cographs | ||
| + | | doi = 10.1007/3-540-52846-6_99 | ||
| + | | title = Proc. 2nd Scandinavian Workshop on Algorithm Theory | ||
| + | | pages = 301–309 | ||
| + | | publisher = Springer-Verlag | ||
| + | | series = Lecture Notes in Computer Science | ||
| + | | volume = 447 | ||
| + | | year = 1990| isbn = 978-3-540-52846-3 | title-link = SWAT and WADS conferences | hdl = 1874/16625 | hdl-access = free | ||
| + | }}. | ||
| + | *{{citation | ||
| + | | last1 = Cattell | first1 = Kevin | ||
| + | | last2 = Dinneen | first2 = Michael J. | ||
| + | | last3 = Fellows | first3 = Michael R. | author3-link = Michael Fellows | ||
| + | | doi = 10.1016/0020-0190(95)00190-5 | ||
| + | | issue = 4 | ||
| + | | journal = [[Information Processing Letters]] | ||
| + | | pages = 197–203 | ||
| + | | title = A simple linear-time algorithm for finding path-decompositions of small width | ||
| + | | volume = 57 | ||
| + | | year = 1996| arxiv = math/9410211| s2cid = 2442557 | ||
| + | }}. | ||
| + | *{{citation | ||
| + | | last1 = Coudert | ||
| + | | first1 = David | ||
| + | | last2 = Huc | ||
| + | | first2 = Florian | ||
| + | | last3 = Mazauric | ||
| + | | first3 = Dorian | ||
| + | | title = A Distributed Algorithm for Computing the Node Search Number in Trees | ||
| + | | journal = [[Algorithmica]] | ||
| + | | volume = 63 | ||
| + | | issue = 1 | ||
| + | | pages = 158-190 | ||
| + | | year = 2012 | ||
| + | | doi = 10.1007/s00453-011-9524-3 | ||
| + | | url = https://hal.inria.fr/inria-00587819/file/paper-noformat.pdf | ||
| + | | accessdate = 2024-01-31 | ||
| + | | archive-date = 2022-01-03 | ||
| + | | archive-url = https://web.archive.org/web/20220103143005/https://hal.inria.fr/inria-00587819/file/paper-noformat.pdf | ||
| + | | dead-url = no | ||
| + | }}. | ||
| + | *{{citation | ||
| + | | last1 = Coudert | ||
| + | | first1 = David | ||
| + | | last2 = Huc | ||
| + | | first2 = Florian | ||
| + | | last3 = Sereni | ||
| + | | first3 = Jean-Sébastien | ||
| + | | doi = 10.1002/jgt.20218 | ||
| + | | issue = 1 | ||
| + | | journal = [[Journal of Graph Theory]] | ||
| + | | pages = 27–41 | ||
| + | | title = Pathwidth of outerplanar graphs | ||
| + | | volume = 55 | ||
| + | | year = 2007 | ||
| + | | url = https://hal.inria.fr/inria-00070220/file/RR-5804.pdf | ||
| + | | accessdate = 2024-01-31 | ||
| + | | archive-date = 2022-01-03 | ||
| + | | archive-url = https://web.archive.org/web/20220103142927/https://hal.inria.fr/inria-00070220/file/RR-5804.pdf | ||
| + | | dead-url = no | ||
| + | }}. | ||
| + | *{{citation | ||
| + | | last = Diestel | first = Reinhard | ||
| + | | doi = 10.1017/S0963548300001450 | ||
| + | | issue = 1 | ||
| + | | journal = [[Combinatorics, Probability and Computing]] | ||
| + | | pages = 27–30 | ||
| + | | title = Graph Minors I: a short proof of the path-width theorem | ||
| + | | volume = 4 | ||
| + | | year = 1995}}. | ||
| + | *{{citation | ||
| + | | last1 = Diestel | first1 = Reinhard | ||
| + | | last2 = Kühn | first2 = Daniela | author2-link = Daniela Kühn | ||
| + | | doi = 10.1016/j.dam.2004.01.010 | ||
| + | | issue = 2 | ||
| + | | journal = [[Discrete Applied Mathematics]] | ||
| + | | pages = 167–182 | ||
| + | | title = Graph minor hierarchies | ||
| + | | volume = 145 | ||
| + | | year = 2005| doi-access = free | ||
| + | }}. | ||
| + | *{{citation | ||
| + | | last1 = Demaine | first1 = Erik D. | author1-link = Erik Demaine | ||
| + | | last2 = Hajiaghayi | first2 = MohammadTaghi | author2-link = Mohammad Hajiaghayi | ||
| + | | last3 = Kawarabayashi | first3 = Ken-ichi | author3-link = Ken-ichi Kawarabayashi | ||
| + | | contribution = Algorithmic graph minor theory: decomposition, approximation, and coloring | ||
| + | | doi = 10.1109/SFCS.2005.14 | ||
| + | | pages = 637–646 | ||
| + | | title = Proc. 46th IEEE Symposium on Foundations of Computer Science (FOCS 2005) | ||
| + | | year = 2005| isbn = 0-7695-2468-0 | title-link = Symposium on Foundations of Computer Science | s2cid = 13238254 }}. | ||
| + | *{{citation | ||
| + | | last1 = Downey | first1 = Rod G. | author1-link = Rod Downey | ||
| + | | last2 = Fellows | first2 = Michael R. | author2-link = Michael Fellows | ||
| + | | isbn = 0-387-94883-X | ||
| + | | publisher = Springer-Verlag | ||
| + | | title = Parameterized Complexity | ||
| + | | year = 1999}}. | ||
| + | *{{citation | ||
| + | | last1 = Dujmović | first1 = V. | author1-link = Vida Dujmović | ||
| + | | last2 = Fellows | first2 = M.R. | author2-link = Michael Fellows | ||
| + | | last3 = Kitching | first3 = M. | ||
| + | | last4 = Liotta | first4 = G. | ||
| + | | last5 = McCartin | first5 = C. | ||
| + | | last6 = Nishimura | first6 = N. | ||
| + | | last7 = Ragde | first7 = P. | ||
| + | | last8 = Rosamond | first8 = F. | ||
| + | | last9 = Whitesides | first9 = S. | author9-link = Sue Whitesides | ||
| + | | last10 = Wood | ||
| + | | first10 = David R. | author10-link = David Wood (mathematician) | ||
| + | | doi = 10.1007/s00453-007-9151-1 | ||
| + | | issue = 2 | ||
| + | | journal = [[Algorithmica]] | ||
| + | | pages = 267–292 | ||
| + | | title = On the parameterized complexity of layered graph drawing | ||
| + | | volume = 52 | ||
| + | | year = 2008 | ||
| + | | s2cid = 2298634 | ||
| + | }}. | ||
| + | *{{citation | ||
| + | | last1 = Dujmović | ||
| + | | first1 = Vida | ||
| + | | author1-link = Vida Dujmović | ||
| + | | last2 = Morin | ||
| + | | first2 = Pat | ||
| + | | author2-link = Pat Morin | ||
| + | | last3 = Wood | ||
| + | | first3 = David R. | ||
| + | | author3-link = David Wood (mathematician) | ||
| + | | contribution = Path-width and three-dimensional straight-line grid drawings of graphs | ||
| + | | pages = 42–53 | ||
| + | | publisher = Springer-Verlag | ||
| + | | series = Lecture Notes in Computer Science | ||
| + | | title = Proc. 10th International Symposium on Graph Drawing (GD 2002) | ||
| + | | contribution-url = http://cg.scs.carleton.ca/~vida/pubs/papers/DMW-GD02.pdf | ||
| + | | volume = 2528 | ||
| + | | year = 2003 | ||
| + | | title-link = International Symposium on Graph Drawing | ||
| + | | accessdate = 2024-01-31 | ||
| + | | archive-date = 2012-03-04 | ||
| + | | archive-url = https://web.archive.org/web/20120304190101/http://cg.scs.carleton.ca/~vida/pubs/papers/DMW-GD02.pdf | ||
| + | | dead-url = no | ||
| + | }}. | ||
| + | *{{citation | ||
| + | | last1 = Ellis | first1 = J. A. | ||
| + | | last2 = Sudborough | first2 = I. H. | ||
| + | | last3 = Turner | first3 = J. S. | ||
| + | | contribution = Graph separation and search number | ||
| + | | title = Proc. 1983 Allerton Conf. on Communication, Control, and Computing | ||
| + | | year = 1983}}. As cited by {{harvtxt|Monien|Sudborough|1988}}. | ||
| + | *{{citation | ||
| + | | last1 = Ellis | first1 = J. A. | ||
| + | | last2 = Sudborough | first2 = I. H. | ||
| + | | last3 = Turner | first3 = J. S. | ||
| + | | doi = 10.1006/inco.1994.1064 | ||
| + | | issue = 1 | ||
| + | | journal = [[Information and Computation]] | ||
| + | | pages = 50–79 | ||
| + | | title = The vertex separation and search number of a tree | ||
| + | | volume = 113 | ||
| + | | year = 1994| doi-access = free | ||
| + | }}. | ||
| + | *{{citation | ||
| + | | last1 = Feige | first1 = Uriel | author1-link = Uriel Feige | ||
| + | | last2 = Hajiaghayi | first2 = Mohammadtaghi | author2-link = Mohammad Hajiaghayi | ||
| + | | last3 = Lee | first3 = James R. | ||
| + | | contribution = Improved approximation algorithms for minimum-weight vertex separators | ||
| + | | doi = 10.1145/1060590.1060674 | ||
| + | | pages = 563–572 | ||
| + | | title = Proc. 37th ACM Symposium on Theory of Computing (STOC 2005) | ||
| + | | year = 2005| isbn = 1581139608 | title-link = Symposium on Theory of Computing | s2cid = 14097859 }}. | ||
| + | *{{citation | ||
| + | | last1 = Fellows | first1 = Michael R. | author1-link = Michael Fellows | ||
| + | | last2 = Langston | first2 = Michael A. | author2-link = Michael Langston | ||
| + | | contribution = On search decision and the efficiency of polynomial-time algorithms | ||
| + | | doi = 10.1145/73007.73055 | ||
| + | | pages = 501–512 | ||
| + | | title = Proc. 21st ACM Symposium on Theory of Computing | ||
| + | | year = 1989| isbn = 0897913078 | title-link = Symposium on Theory of Computing | s2cid = 1854173 | doi-access = free}}. | ||
| + | *{{citation | ||
| + | | last1 = Ferreira | first1 = Afonso G. | ||
| + | | last2 = Song | first2 = Siang W. | ||
| + | | contribution = Achieving optimality for gate matrix layout and PLA folding: a graph theoretic approach | ||
| + | | doi = 10.1007/BFb0023825 | ||
| + | | pages = 139–153 | ||
| + | | publisher = Springer-Verlag | ||
| + | | series = Lecture Notes in Computer Science | ||
| + | | title = Proc. 1st Latin American Symposium on Theoretical Informatics (LATIN '92) | ||
| + | | volume = 583 | ||
| + | | year = 1992| isbn = 3-540-55284-7 | ||
| + | | hdl = 10068/43314 | ||
| + | | hdl-access = free | ||
| + | }}. | ||
| + | *{{citation | ||
| + | | last = de Fluiter | ||
| + | | first = Babette | ||
| + | | isbn = 90-393-1528-0 | ||
| + | | publisher = [[Utrecht University]] | ||
| + | | series = Ph.D. thesis | ||
| + | | title = Algorithms for Graphs of Small Treewidth | ||
| + | | url = http://igitur-archive.library.uu.nl/dissertations/01847381/full.pdf | ||
| + | | year = 1997 | ||
| + | | access-date = 2010-05-06 | ||
| + | | archive-url = https://web.archive.org/web/20110724173550/http://igitur-archive.library.uu.nl/dissertations/01847381/full.pdf | ||
| + | | archive-date = 2011-07-24 | ||
| + | | url-status = dead | ||
| + | }}. | ||
| + | *{{citation | ||
| + | | last = Fomin | first = Fedor V. | ||
| + | | doi = 10.1007/s00373-002-0490-z | ||
| + | | issue = 1 | ||
| + | | journal = [[Graphs and Combinatorics]] | ||
| + | | pages = 91–99 | ||
| + | | title = Pathwidth of planar and line graphs | ||
| + | | volume = 19 | ||
| + | | year = 2003| s2cid = 43123449 | ||
| + | }}. | ||
| + | *{{citation | ||
| + | | last1 = Fomin | first1 = Fedor V. | ||
| + | | last2 = Høie | first2 = Kjartan | ||
| + | | doi = 10.1016/j.ipl.2005.10.012 | ||
| + | | issue = 5 | ||
| + | | journal = [[Information Processing Letters]] | ||
| + | | pages = 191–196 | ||
| + | | title = Pathwidth of cubic graphs and exact algorithms | ||
| + | | volume = 97 | ||
| + | | year = 2006}}. | ||
| + | *{{citation | ||
| + | | last1 = Fomin | first1 = Fedor V. | ||
| + | | last2 = Kratsch | first2 = Dieter | ||
| + | | last3 = Todinca | first3 = Ioan | ||
| + | | last4 = Villanger | first4 = Yngve | ||
| + | | doi = 10.1137/050643350 | ||
| + | | issue = 3 | ||
| + | | journal = [[SIAM Journal on Computing]] | ||
| + | | pages = 1058–1079 | ||
| + | | title = Exact algorithms for treewidth and minimum fill-in | ||
| + | | volume = 38 | ||
| + | | year = 2008| hdl = 1956/1151 | ||
| + | | hdl-access = free | ||
| + | }}. | ||
| + | *{{citation | ||
| + | | last1 = Fomin | first1 = Fedor V. | ||
| + | | last2 = Thilikos | first2 = Dimitrios M. | ||
| + | | doi = 10.1002/jgt.20219 | ||
| + | | issue = 1 | ||
| + | | journal = [[Journal of Graph Theory]] | ||
| + | | pages = 42–54 | ||
| + | | title = On self duality of pathwidth in polyhedral graph embeddings | ||
| + | | volume = 55 | ||
| + | | year = 2007}}. | ||
| + | *{{citation | ||
| + | | last = Garbe | first = Renate | ||
| + | | contribution = Tree-width and path-width of comparability graphs of interval orders | ||
| + | | doi = 10.1007/3-540-59071-4_35 | ||
| + | | pages = 26–37 | ||
| + | | publisher = Springer-Verlag | ||
| + | | series = Lecture Notes in Computer Science | ||
| + | | title = Proc. 20th International Workshop Graph-Theoretic Concepts in Computer Science (WG'94) | ||
| + | | volume = 903 | ||
| + | | year = 1995| isbn = 978-3-540-59071-2 | ||
| + | }}. | ||
| + | *{{citation | ||
| + | | last = Golovach | first = P. A. | ||
| + | | doi = 10.1515/dma.1993.3.5.517 | ||
| + | | issue = 5 | ||
| + | | journal = Discrete Mathematics and Applications | ||
| + | | pages = 517–522 | ||
| + | | title = The cutwidth of a graph and the vertex separation number of the line graph | ||
| + | | volume = 3 | ||
| + | | year = 1993| s2cid = 120745961 | ||
| + | }}. | ||
| + | *{{citation | ||
| + | | last = Guha | first = Sudipto | ||
| + | | doi = 10.1109/SFCS.2000.892072 | ||
| + | | title = Proc. 41st IEEE Symposium on Foundations of Computer Science (FOCS 2000) | ||
| + | | page = 126 | ||
| + | | contribution = Nested graph dissection and approximation algorithms | ||
| + | | year = 2000| isbn = 0-7695-0850-2 | ||
| + | | title-link = Symposium on Foundations of Computer Science | ||
| + | | s2cid = 9854056 | ||
| + | }}. | ||
| + | *{{citation | ||
| + | | last1 = Gurski | first1 = Frank | ||
| + | | last2 = Wanke | first2 = Egon | ||
| + | | doi = 10.1016/j.disc.2007.01.020 | ||
| + | | issue = 22 | ||
| + | | journal = [[Discrete Mathematics (journal)|Discrete Mathematics]] | ||
| + | | pages = 2734–2754 | ||
| + | | title = Line graphs of bounded clique-width | ||
| + | | volume = 307 | ||
| + | | year = 2007| doi-access = free | ||
| + | }}. | ||
| + | *{{citation | ||
| + | | last = Gustedt | first = Jens | ||
| + | | doi = 10.1016/0166-218X(93)90012-D | ||
| + | | issue = 3 | ||
| + | | journal = [[Discrete Applied Mathematics]] | ||
| + | | pages = 233–248 | ||
| + | | title = On the pathwidth of chordal graphs | ||
| + | | volume = 45 | ||
| + | | year = 1993| doi-access = free | ||
| + | }}. | ||
| + | *{{citation | ||
| + | | last1 = Habib | first1 = Michel | ||
| + | | last2 = Möhring | first2 = Rolf H. | ||
| + | | doi = 10.1007/BF01462229 | ||
| + | | issue = 1 | ||
| + | | journal = [[Order (journal)|Order]] | ||
| + | | pages = 47–60 | ||
| + | | title = Treewidth of cocomparability graphs and a new order-theoretic parameter | ||
| + | | volume = 11 | ||
| + | | year = 1994| s2cid = 2648030 | ||
| + | }}. | ||
| + | *{{citation | ||
| + | | last = Hliněny | first = Petr | ||
| + | | doi = 10.1016/S0095-8956(03)00037-6 | ||
| + | | issue = 2 | ||
| + | | journal = [[Journal of Combinatorial Theory|Journal of Combinatorial Theory, Series B]] | ||
| + | | pages = 347–367 | ||
| + | | title = Crossing-number critical graphs have bounded path-width | ||
| + | | volume = 88 | ||
| + | | year = 2003| doi-access = free | ||
| + | }}. | ||
| + | *{{citation | ||
| + | | last1 = Kashiwabara | first1 = T. | ||
| + | | last2 = Fujisawa | first2 = T. | ||
| + | | contribution = NP-completeness of the problem of finding a minimum-clique-number interval graph containing a given graph as a subgraph | ||
| + | | pages = 657–660 | ||
| + | | title = Proc. International Symposium on Circuits and Systems | ||
| + | | year = 1979| title-link = International Symposium on Circuits and Systems | ||
| + | }}. | ||
| + | *{{citation | ||
| + | | last = Kinnersley | first = Nancy G. | ||
| + | | doi = 10.1016/0020-0190(92)90234-M | ||
| + | | issue = 6 | ||
| + | | journal = [[Information Processing Letters]] | ||
| + | | pages = 345–350 | ||
| + | | title = The vertex separation number of a graph equals its path-width | ||
| + | | volume = 42 | ||
| + | | year = 1992| doi-access = free | ||
| + | }}. | ||
| + | *{{citation | ||
| + | | last1 = Kinnersley | first1 = Nancy G. | ||
| + | | last2 = Langston | first2 = Michael A. | author2-link = Michael Langston | ||
| + | | doi = 10.1016/0166-218X(94)90021-3 | ||
| + | | issue = 2–3 | ||
| + | | journal = [[Discrete Applied Mathematics]] | ||
| + | | pages = 169–213 | ||
| + | | title = Obstruction set isolation for the gate matrix layout problem | ||
| + | | volume = 54 | ||
| + | | year = 1994| doi-access = free | ||
| + | }}. | ||
| + | *{{citation | ||
| + | |last1 = Kirousis | ||
| + | |first1 = Lefteris M. | ||
| + | |last2 = Papadimitriou | ||
| + | |first2 = Christos H. | ||
| + | |author2-link = Christos Papadimitriou | ||
| + | |doi = 10.1016/0012-365X(85)90046-9 | ||
| + | |issue = 2 | ||
| + | |journal = [[Discrete Mathematics (journal)|Discrete Mathematics]] | ||
| + | |pages = 181–184 | ||
| + | |title = Interval graphs and searching | ||
| + | |url = http://lca.ceid.upatras.gr/~kirousis/publications/j31.pdf | ||
| + | |archive-url = https://web.archive.org/web/20110721084127/http://lca.ceid.upatras.gr/~kirousis/publications/j31.pdf | ||
| + | |url-status = dead | ||
| + | |archive-date = 2011-07-21 | ||
| + | |volume = 55 | ||
| + | |year = 1985 | ||
| + | |doi-access= free | ||
| + | }}. | ||
| + | *{{citation | ||
| + | | last1 = Kloks | first1 = Ton | ||
| + | | last2 = Bodlaender | first2 = Hans L. | author2-link = Hans L. Bodlaender | ||
| + | | contribution = Approximating treewidth and pathwidth of some classes of perfect graphs | ||
| + | | doi = 10.1007/3-540-56279-6_64 | ||
| + | | pages = 116–125 | ||
| + | | publisher = Springer-Verlag | ||
| + | | title = Proc. 3rd International Symposium on Algorithms and Computation (ISAAC'92) | ||
| + | | series = Lecture Notes in Computer Science | ||
| + | | year = 1992 | ||
| + | | volume = 650| isbn = 978-3-540-56279-5 | ||
| + | | hdl = 1874/16672 | ||
| + | | hdl-access = free | ||
| + | }}. | ||
| + | *{{citation | ||
| + | | last1 = Kloks | first1 = T. | ||
| + | | last2 = Bodlaender | first2 = H. | author2-link = Hans L. Bodlaender | ||
| + | | last3 = Müller | first3 = H. | ||
| + | | last4 = Kratsch | first4 = D. | ||
| + | | contribution = Computing treewidth and minimum fill-in: all you need are the minimal separators | ||
| + | | doi = 10.1007/3-540-57273-2_61 | ||
| + | | pages = 260–271 | ||
| + | | publisher = Springer-Verlag | ||
| + | | title = Proc. 1st European Symposium on Algorithms (ESA'93) (Lecture Notes in Computer Science) | ||
| + | | volume = 726 | ||
| + | | year = 1993 | ||
| + | | title-link = European Symposium on Algorithms | ||
| + | }}. | ||
| + | *{{citation | ||
| + | | last1 = Kloks | first1 = Ton | ||
| + | | last2 = Kratsch | first2 = Dieter | ||
| + | | last3 = Müller | first3 = H. | ||
| + | | contribution = Dominoes | ||
| + | | doi = 10.1007/3-540-59071-4_41 | ||
| + | | pages = 106–120 | ||
| + | | publisher = Springer-Verlag | ||
| + | | series = Lecture Notes in Computer Science | ||
| + | | title = Proc. 20th International Workshop Graph-Theoretic Concepts in Computer Science (WG'94) | ||
| + | | volume = 903 | ||
| + | | year = 1995| isbn = 978-3-540-59071-2 | ||
| + | }}. | ||
| + | *{{citation | ||
| + | | last1 = Kneis | first1 = Joachim | ||
| + | | last2 = Mölle | first2 = Daniel | ||
| + | | last3 = Richter | first3 = Stefan | ||
| + | | last4 = Rossmanith | first4 = Peter | ||
| + | | contribution = Algorithms based on the treewidth of sparse graphs | ||
| + | | doi = 10.1007/11604686_34 | ||
| + | | pages = 385–396 | ||
| + | | publisher = Springer-Verlag | ||
| + | | series = Lecture Notes in Computer Science | ||
| + | | title = Proc. 31st International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2005) | ||
| + | | volume = 3787 | ||
| + | | year = 2005| isbn = 978-3-540-31000-6 | ||
| + | }}. | ||
| + | *{{citation | ||
| + | | last1 = Korach | first1 = Ephraim | ||
| + | | last2 = Solel | first2 = Nir | ||
| + | | doi = 10.1016/0166-218X(93)90171-J | ||
| + | | issue = 1 | ||
| + | | journal = [[Discrete Applied Mathematics]] | ||
| + | | pages = 97–101 | ||
| + | | title = Tree-width, path-width, and cutwidth | ||
| + | | volume = 43 | ||
| + | | year = 1993| doi-access = free | ||
| + | }}. | ||
| + | *{{citation | ||
| + | | last1 = Kornai | first1 = András | ||
| + | | last2 = Tuza | first2 = Zsolt | ||
| + | | doi = 10.1016/0166-218X(92)90208-R | ||
| + | | issue = 1 | ||
| + | | journal = [[Discrete Applied Mathematics]] | ||
| + | | pages = 87–92 | ||
| + | | title = Narrowness, path-width, and their application in natural language processing | ||
| + | | volume = 36 | ||
| + | | year = 1992| doi-access = free | ||
| + | }}. | ||
| + | *{{citation | ||
| + | | last = Lengauer | first = Thomas | ||
| + | | doi = 10.1007/BF00264496 | ||
| + | | issue = 4 | ||
| + | | journal = [[Acta Informatica]] | ||
| + | | pages = 465–475 | ||
| + | | title = Black-white pebbles and graph separation | ||
| + | | volume = 16 | ||
| + | | year = 1981| s2cid = 19415148 | ||
| + | }}. | ||
| + | *{{citation | ||
| + | | last1 = Lopez | first1 = Alexander D. | ||
| + | | last2 = Law | first2 = Hung-Fai S. | ||
| + | | issue = 8 | ||
| + | | journal = IEEE Transactions on Electron Devices | ||
| + | | pages = 1671–1675 | ||
| + | | title = A dense gate matrix layout method for MOS VLSI | ||
| + | | volume = 27 | ||
| + | | year = 1980 | ||
| + | | doi = 10.1109/T-ED.1980.20086 | ||
| + | | id = Also in the joint issue, ''IEEE Journal of Solid-State Circuits'' '''15''' (4): 736–740, 1980| bibcode = 1980ITED...27.1671L | ||
| + | | s2cid = 64469353 | ||
| + | }}. | ||
| + | *{{citation | ||
| + | | last = Miller | ||
| + | | first = George A. | ||
| + | | author-link = George Armitage Miller | ||
| + | | issue = 2 | ||
| + | | journal = [[Psychological Review]] | ||
| + | | pages = 81–97 | ||
| + | | title = The Magical Number Seven, Plus or Minus Two | ||
| + | | url = http://www.musanim.com/miller1956/ | ||
| + | | volume = 63 | ||
| + | | year = 1956 | ||
| + | | doi = 10.1037/h0043158 | ||
| + | | pmid = 13310704 | ||
| + | | hdl = 11858/00-001M-0000-002C-4646-B | ||
| + | | hdl-access = free | ||
| + | | accessdate = 2024-01-31 | ||
| + | | archive-date = 2008-05-30 | ||
| + | | archive-url = https://web.archive.org/web/20080530073121/http://www.musanim.com/miller1956/ | ||
| + | | dead-url = no | ||
| + | }}. | ||
| + | *{{citation | ||
| + | | last = Möhring | first = Rolf H. | ||
| + | | contribution = Graph problems related to gate matrix layout and PLA folding | ||
| + | | editor1-last = Tinhofer | editor1-first = G. | ||
| + | | editor2-last = Mayr | editor2-first = E. | ||
| + | | editor3-last = Noltemeier | editor3-first = H. | ||
| + | |display-editors = 3 | editor4-last = Sysło | editor4-first = M. | ||
| + | | isbn = 3-211-82177-5 | ||
| + | | pages = 17–51 | ||
| + | | publisher = Springer-Verlag | ||
| + | | series = Computing Supplementum | ||
| + | | title = Computational Graph Theory | ||
| + | | volume = 7 | ||
| + | | year = 1990}}. | ||
| + | *{{citation | ||
| + | | last1 = Monien | first1 = B. | ||
| + | | last2 = Sudborough | first2 = I. H. | ||
| + | | doi = 10.1016/0304-3975(88)90028-X | ||
| + | | issue = 1–3 | ||
| + | | journal = [[Theoretical Computer Science (journal)|Theoretical Computer Science]] | ||
| + | | pages = 209–229 | ||
| + | | title = Min cut is NP-complete for edge weighted trees | ||
| + | | volume = 58 | ||
| + | | year = 1988| doi-access = free | ||
| + | }}. | ||
| + | *{{citation | ||
| + | | last1 = Ohtsuki | first1 = Tatsuo | ||
| + | | last2 = Mori | first2 = Hajimu | ||
| + | | last3 = Kuh | first3 = Ernest S. | ||
| + | | last4 = Kashiwabara | first4 = Toshinobu | ||
| + | | last5 = Fujisawa | first5 = Toshio | ||
| + | | doi = 10.1109/TCS.1979.1084695 | ||
| + | | issue = 9 | ||
| + | | journal = IEEE Transactions on Circuits and Systems | ||
| + | | pages = 675–684 | ||
| + | | title = One-dimensional logic gate assignment and interval graphs | ||
| + | | volume = 26 | ||
| + | | year = 1979}}. | ||
| + | *{{citation | ||
| + | | last1 = Peng | first1 = Sheng-Lung | ||
| + | | last2 = Ho | first2 = Chin-Wen | ||
| + | | last3 = Hsu | first3 = Tsan-sheng | ||
| + | | last4 = Ko | first4 = Ming-Tat | ||
| + | | last5 = Tang | first5 = Chuan Yi | ||
| + | | contribution = A linear-time algorithm for constructing an optimal node-search strategy of a tree | ||
| + | | pages = 197–205 | ||
| + | | publisher = Springer-Verlag | ||
| + | | series = Lecture Notes in Computer Science | ||
| + | | title = Proc. 4th Int. Conf. Computing and Combinatorics (COCOON'98) | ||
| + | | url = http://www.springerlink.com/content/lamc6dynulxv7a8n/ | ||
| + | | volume = 1449 | ||
| + | | year = 1998}}{{dead link|date=May 2020|bot=medic}}{{cbignore|bot=medic}}. | ||
| + | *{{citation | ||
| + | | last1 = Proskurowski | ||
| + | | first1 = Andrzej | ||
| + | | last2 = Telle | ||
| + | | first2 = Jan Arne | ||
| + | | journal = Discrete Mathematics and Theoretical Computer Science | ||
| + | | pages = 167–176 | ||
| + | | title = Classes of graphs with restricted interval models | ||
| + | | url = http://www.emis.de/journals/DMTCS/volumes/abstracts/pdfpapers/dm030404.pdf | ||
| + | | volume = 3 | ||
| + | | year = 1999 | ||
| + | | accessdate = 2024-01-31 | ||
| + | | archive-date = 2024-01-31 | ||
| + | | archive-url = https://web.archive.org/web/20240131132545/https://www.emis.de/journals/DMTCS/volumes/abstracts/pdfpapers/dm030404.pdf | ||
| + | | dead-url = no | ||
| + | }}. | ||
| + | *{{citation | ||
| + | | last1 = Robertson | first1 = Neil | author1-link = Neil Robertson (mathematician) | ||
| + | | last2 = Seymour | first2 = Paul | author2-link = Paul Seymour (mathematician) | ||
| + | | doi = 10.1016/0095-8956(83)90079-5 | ||
| + | | issue = 1 | ||
| + | | journal = [[Journal of Combinatorial Theory|Journal of Combinatorial Theory, Series B]] | ||
| + | | pages = 39–61 | ||
| + | | title = Graph minors. I. Excluding a forest | ||
| + | | volume = 35 | ||
| + | | year = 1983| doi-access = free | ||
| + | }}. | ||
| + | *{{citation | ||
| + | | last1 = Robertson | first1 = Neil | author1-link = Neil Robertson (mathematician) | ||
| + | | last2 = Seymour | first2 = Paul | author2-link = Paul Seymour (mathematician) | ||
| + | | doi = 10.1016/S0095-8956(03)00042-X | ||
| + | | issue = 1 | ||
| + | | journal = [[Journal of Combinatorial Theory|Journal of Combinatorial Theory, Series B]] | ||
| + | | pages = 43–76 | ||
| + | | title = Graph minors. XVI. Excluding a non-planar graph | ||
| + | | volume = 89 | ||
| + | | year = 2003| doi-access = free | ||
| + | }}. | ||
| + | *{{citation | ||
| + | | last1 = Robertson | first1 = Neil | author1-link = Neil Robertson (mathematician) | ||
| + | | last2 = Seymour | first2 = Paul D. | author2-link = Paul Seymour (mathematician) | ||
| + | | doi = 10.1016/j.jctb.2004.08.001 | ||
| + | | issue = 2 | ||
| + | | journal = [[Journal of Combinatorial Theory|Journal of Combinatorial Theory, Series B]] | ||
| + | | pages = 325–357 | ||
| + | | title = Graph Minors. XX. Wagner's conjecture | ||
| + | | volume = 92 | ||
| + | | year = 2004| doi-access = free | ||
| + | }}. | ||
| + | *{{citation | ||
| + | | last = Scheffler | first = Petra | ||
| + | | contribution = A linear algorithm for the pathwidth of trees | ||
| + | | editor1-last = Bodendiek | editor1-first = R. | ||
| + | | editor2-last = Henn | editor2-first = R. | ||
| + | | pages = 613–620 | ||
| + | | publisher = Physica-Verlag | ||
| + | | title = Topics in Combinatorics and Graph Theory | ||
| + | | year = 1990}}. | ||
| + | *{{citation | ||
| + | | last = Scheffler | first = Petra | ||
| + | | contribution = Optimal embedding of a tree into an interval graph in linear time | ||
| + | | editor1-last = Nešetřil | editor1-first = Jaroslav | editor1-link = Jaroslav Nešetřil | ||
| + | | editor2-last = Fiedler | editor2-first = Miroslav | ||
| + | | publisher = Elsevier | ||
| + | | title = Fourth Czechoslovakian Symposium on Combinatorics, Graphs and Complexity | ||
| + | | year = 1992 | ||
| + | }}. | ||
| + | *{{citation | ||
| + | | last = Skodinis | first = Konstantin | ||
| + | | contribution = Computing optimal linear layouts of trees in linear time | ||
| + | | doi = 10.1007/3-540-45253-2_37 | ||
| + | | pages = 403–414 | ||
| + | | publisher = Springer-Verlag | ||
| + | | series = Lecture Notes in Computer Science | ||
| + | | title = Proc. 8th European Symposium on Algorithms (ESA 2000) | ||
| + | | volume = 1879 | ||
| + | | year = 2000| isbn = 978-3-540-41004-1 | ||
| + | | title-link = European Symposium on Algorithms | ||
| + | }}. | ||
| + | *{{citation | ||
| + | | last = Skodinis | first = Konstantin | ||
| + | | doi = 10.1016/S0196-6774(02)00225-0 | ||
| + | | issue = 1 | ||
| + | | journal = Journal of Algorithms | ||
| + | | pages = 40–59 | ||
| + | | title = Construction of linear tree-layouts which are optimal with respect to vertex separation in linear time | ||
| + | | volume = 47 | ||
| + | | year = 2003}}. | ||
| + | *{{citation | ||
| + | | last1 = Suchan | first1 = Karol | ||
| + | | last2 = Todinca | first2 = Ioan | ||
| + | | contribution = Pathwidth of circular-arc graphs | ||
| + | | doi = 10.1007/978-3-540-74839-7_25 | ||
| + | | pages = 258–269 | ||
| + | | publisher = Springer-Verlag | ||
| + | | series = Lecture Notes in Computer Science | ||
| + | | title = Proc. 33rd International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2007) | ||
| + | | volume = 4769 | ||
| + | | year = 2007 | ||
| + | }}. | ||
| + | *{{citation | ||
| + | |last = Suderman | ||
| + | |first = Matthew | ||
| + | |doi = 10.1142/S0218195904001433 | ||
| + | |issue = 3 | ||
| + | |journal = [[International Journal of Computational Geometry and Applications]] | ||
| + | |pages = 203–225 | ||
| + | |title = Pathwidth and layered drawings of trees | ||
| + | |url = http://cgm.cs.mcgill.ca/~msuder/schools/mcgill/research/trees/SOCS-02-8.pdf | ||
| + | |volume = 14 | ||
| + | |year = 2004 | ||
| + | |url-status = dead | ||
| + | |archive-url = https://web.archive.org/web/20030503103911/http://cgm.cs.mcgill.ca/~msuder/schools/mcgill/research/trees/SOCS-02-8.pdf | ||
| + | |archive-date = 2003-05-03 | ||
| + | }}. | ||
| + | *{{citation | ||
| + | | last1 = Takahashi | first1 = Atsushi | ||
| + | | last2 = Ueno | first2 = Shuichi | ||
| + | | last3 = Kajitani | first3 = Yoji | ||
| + | | doi = 10.1016/0012-365X(94)90092-2 | ||
| + | | issue = 1–3 | ||
| + | | journal = [[Discrete Mathematics (journal)|Discrete Mathematics]] | ||
| + | | pages = 293–304 | ||
| + | | title = Minimal acyclic forbidden minors for the family of graphs with bounded path-width | ||
| + | | volume = 127 | ||
| + | | year = 1994| doi-access = free | ||
| + | }}. | ||
| + | {{refend}} | ||
| + | |||
| + | [[Category:图论]] | ||
| + | [[Category:图常量]] | ||
2025年6月21日 (六) 17:04的版本
图论中，图G的径分解（path decomposition）是G的“加粗”路径图表示，[1]G的径宽（pathwidth）是衡量形成G的路径被加粗的程度。更正式地说，径分解是G的顶点子集序列，使每条边的端点出现在某一子集中，并使每个顶点都出现在子集连续子序列中，[2]径宽等于这样的分解中最大集的大小减一。 径宽也叫做区间厚度（interval thickness，等于G的区间父图中的最大团大小减一）、顶点分隔数（vertex separation number）或结点搜索数（node searching number）。[3]
径宽与径分解同树宽、树分解关系密切，在图子式理论中起关键作用：在图子式下封闭、不含所有森林的图族可描述为径宽有界，[2]子式闭图族的一般结构理论中出现的“涡”（vortex）的径宽也有界。[4]径宽与径宽有界图在超大规模集成电路设计、图绘制、计算语言学等领域也有应用。
计算任意图的径宽、甚至精确近似径宽都是NP困难的。[5][6]不过，这问题是固定参数可解的：测试图的径宽是否为k，耗时与图的大小呈线性关系，而与k呈上指数关系。[7]另外，对树之类的特殊图，径宽可在多项式时间内算得，而不依赖于k。模板:Sfnp[8] 对图的径分解使用动态规划，可以将图算法中很多问题在径宽有界图上高效解决。[9]径分解也可测量树宽有界图上动态规划算法的空间复杂度。[10]
定义
文件:Pathwidth.JPG
径宽为2的例图G，其径分解宽度为2。图像下半部是相同的图与径分解，添加了颜色以示强调。（本例改编自模板:Harvp，添加了记号）
模板:Harvs在图子式系列论文的第一篇中，将图G的径分解定义为G的顶点子集[math]\displaystyle{ X_i }[/math]序列，满足两条属性：
- 对G中每条边，存在i使边的两端点都属于子集[math]\displaystyle{ X_i }[/math]；
- [math]\displaystyle{ \forall i\le j\le k,\ X_i \cap X_k \subseteq X_j. }[/math]
第二条性质等价于要求包含任意特定顶点的子集构成整个序列的连续子列。用系列论文后期的话来说，径分解是树分解[math]\displaystyle{ (X,\ T) }[/math]，其中分解的底树T是路径图。 径分解的宽度与树分解类似，是[math]\displaystyle{ {\rm max}_i|X_i|-1 }[/math]，G的径宽是G的径分解的最小宽度。在径宽的大多数应用中，[math]\displaystyle{ X_i }[/math]的大小减不减一没什么差别，主要是为了使路径图的径宽等于1。
其他特征
如Bodlaender (1998)所描述的，径宽可用许多等价方法表征。
粘合序列
径分解可表述为图[math]\displaystyle{ G_i }[/math]的序列，找到来自序列中连续图的顶点对，并将图粘合在一起，所有粘合的结果就是G。在径分解的第一个定义中，图[math]\displaystyle{ G_i }[/math]可看作是集合[math]\displaystyle{ X_i }[/math]的诱导子图，连续（successive）诱导子图中的两顶点被G中相同顶点诱导时，就会被粘在一起；反之，可以把集合[math]\displaystyle{ X_i }[/math]恢复为图[math]\displaystyle{ G_i }[/math]的顶点集。则径分解的宽度比某一图[math]\displaystyle{ G_i }[/math]的最大顶点数少1。[2]
区间厚度
径宽为2的区间图，而4个最大团ABC、ACD、CDE、CDF的大小为3。
任意图G的径宽等于含G（以G为子图）的区间图的最小团数减一。[11]即，对G的每种径分解，都能找到G的区间子图；对G的每个区间父图，都能找到G的径分解，使分解的宽度比区间图团数小1。
假设给出了G的径分解。则可将分解的结点表为直线上的点（按路径顺序），并将每个顶点v表示为以这些点为端点的闭区间。这样，包含v的径分解结点就对应v在区间中的代表点。G顶点形成的区间交图是包含G的区间图，其最大团由包含代表点的区间集给出，大小比G的径宽大1。
设G是某区间图的子图，团数[math]\displaystyle{ p+1 }[/math]，则G有宽p的径分解，其结点由区间图的最大团给出。例如，图中的区间图及其区间表示的径分解有5个结点，分别对应5个最大团ABC、ACD、CDE、CDF、FG；最大团大小为3，这径分解的宽度为2。 径宽与区间厚度之间的等价关系同树宽与弦图（给定图是弦图的子图）的最小团数（减一）的等价关系非常相似。区间图是弦图的特例，弦图可表为共同树的子树的交图，这类似于区间图是路径子径的交图。
顶点分隔数
设图G的顶点是线性有序的。则，G的顶点分隔数是满足下列条件的最小数s：对顶点v，最多s个顶点在排序中先于v，但有v或更靠后的顶点相邻。 G的顶点分隔数是G的任意线性排序的最小顶点分隔数。顶点分隔数由Ellis, Sudborough & Turner (1983)定义，等于G的径宽。[12] 这源于前述的与区间图团数的等价关系：若G是区间图I的子图，并以所有区间端点都分离的方式表示（如图所示），则I的区间左端点排序的顶点分隔数比I的团数小1。反过来，从G的线性排序可推导出一种区间表示：顶点v的区间左端点是其在排序中的位置，右端点是v在排序中最后一个邻居的位置。
结点搜索数
图上的结点搜索策略是追逃对策的一种形式，当中一组搜索者合作追踪藏在图中的逃犯。搜索者被置于图的顶点上，逃犯可能在任意边上，位置与移动对搜索者不可见。每个回合中，搜索者的部分或全部可从顶点移动到另一顶点（任意移动，不必沿边），逃犯可以沿不经过搜索者顶点的任意路径移动。逃犯所在边的两端点都被搜索者占据时，就被抓获。图的结点搜索数是必然能抓到逃犯的最少搜索者数。如Kirousis & Papadimitriou (1985)所示，图的结点搜索数等于其区间厚度。搜索者的最优策略是不断移动搜索者，使他们在连续回合中形成具有最小顶点分隔数的线性排序的分隔集。
界
毛虫树，径宽为1的最大图。
径宽为k的n顶点图至多有[math]\displaystyle{ k(n-k+\frac{k-1}{2}) }[/math]条边，是最大k径宽图（即径宽为k、无论怎样添加边都必改变径宽的图）的边数。径宽为k的最大图要么是k径图要么是k毛虫图，它们是两种特殊的k树。k树是恰有[math]\displaystyle{ n-k }[/math]个最大团（含[math]\displaystyle{ k+1 }[/math]个顶点）的弦图；在本身不是[math]\displaystyle{ (k+1) }[/math]团的k树中，每个最大团要么将图分隔成多个部分，要么包含单个叶顶点（只属于一个最大团的顶点）。k径图是至少有两叶的k树，k毛虫图是可分割维k径与一组k叶的k树，其中每片叶还与k径中的独立k团相邻。径宽为1的最大图是毛虫树。[13]
由于径分解是树分解的特例，径宽不小于树宽，且不大于割宽，即在图顶点的最优线性排列中，前后顶点组之间割边的最小数。这是因为，顶点分隔数即前后顶点组的邻接数不大于割边数。[14]出于类似原因，割宽不大于径宽乘顶点的最大度。[15]
任意n顶点森林都有径宽[math]\displaystyle{ O(\log n) }[/math]。[16]例如，对一个森林，总能找到恒定多的顶点，使得去掉它们后形成至多有[math]\displaystyle{ \frac{2n}{3} }[/math]个顶点的两片子森林。如此递归地分隔子森林，将分隔顶点置于两者之间，形成的线性排列具有对数顶点搜索数。此技术用于树分解时，可知，若n顶点图G的树宽为t，则G的径宽是[math]\displaystyle{ O(t\log n) }[/math]。[17]由于外平面图、系列并行图、哈林图的树宽都有界，它们的径宽最多为对数的。
此外，径宽还通过线图，同团宽与割宽有关系。G的边在其线图[math]\displaystyle{ L(G) }[/math]中都有对应的顶点，当G中相应的两边有共同端点时，[math]\displaystyle{ L(G) }[/math]中的两顶点就是相邻的。当且仅当图族的线图的线性团宽（用邻接1个新顶点的操作取代了团宽的不交并操作）有界，图族的径宽有界。[18]若某3及以上个顶点的连通图的最大度为3，则其割宽等于线图的顶点分隔数。[19]
平面图的径宽最多与顶点数的平方根成正比。[20]找到具有这种宽度的径分解，一种方法是（与上述森林的对数宽径分解类似）用平面分隔定理找到[math]\displaystyle{ O(\sqrt n) }[/math]个顶点的集合，其将图分隔为至多有[math]\displaystyle{ \frac{2n}{3} }[/math]个顶点的两个子图，如此递归地分隔子图，最后将两子图的递归径分解连接起来。同样的技术也适用于类似分离器定理成立的任何一类图。[21]与平面图一样，任何固定的子式闭图族中的图都有大小为[math]\displaystyle{ O(\sqrt n) }[/math]的分隔子，[22]因此此类图族中图的径宽也是[math]\displaystyle{ O(\sqrt n) }[/math]。对某类平面图，图的径宽与其对偶图的径宽必须在一常数因子范围内，对于双连通外平面图[23]与多面体图[24]，这种形式的边界是已知的。2连通平面图的对偶图的径宽小于线图的径宽。[25]至于在其他情形下，平面图径宽与对偶图径宽是否总相差某常数因子，仍是未知的。
在某些类的图中，径宽与树宽总相等。已证明的有余图、[26]置换图、[27]可比图之补、[28]区间序的可比图。[29]
模板:Unsolved 在立方图中，或更广义地在任何最大顶点度为3的图中，径宽不大于[math]\displaystyle{ \frac{n}{6}+o(n) }[/math]，其中n是顶点数。存在径宽为[math]\displaystyle{ 0.082n }[/math]的立方图，但如何缩小这下界与上界[math]\displaystyle{ \frac{n}{6} }[/math]之间的差距，目前还不得而知。[30]
计算径分解
确定给定图的径宽是否大于k的问题是NP完全的（k也是输入）。[5]计算任意n顶点图径宽的最坏情形的最优时间边界为[math]\displaystyle{ O(2^nn^c) }[/math]，c是常数。[31]不过，已经有几种算法可在径宽较小、输入图类别有限或近似的情形下更高效地计算径分解。
固定参数可解
径宽是固定参数可解的：对任意常数k，都可测试径宽是否大于k，若不大于k，则在线性时间内找到宽k的径分解。[7]一般来说，这类算法分两阶段运行。第一阶段，假设图的径宽为k，以找到并非最优的径分解或树分解，宽度可作为k的函数而变为约束。第二阶段，对这分解运用动态规划算法，以找到最优分解。然而，已知的这类算法的时间界限是[math]\displaystyle{ k^2 }[/math]的指数级，除了最小的k外，都是不切实际的。[32]对于[math]\displaystyle{ k=2 }[/math]的情形，de Fluiter (1997)给出了基于2径宽图的结构分解的精确限行时间算法。
特殊图类
模板:Harvp调查了计算各种特殊图类的径宽的复杂性。若图G是有界度图、[33]平面图、[33]有界度平面图、[33]弦图、[34]弦多米诺、[35]可比图之补、[28]二分距离遗传图[36]，确定图G的径宽是否最大是k的问题仍是NP完全的。对于包含二分距离遗传图的图族（二分图、弦二分图、距离遗传图、循环图之类），也是NP完全的。[36]
不过，对于树与森林，径宽可在线性时间内算得。[8]对树宽有界图族（系列并行图、外平面图、哈林图）[7]、裂图[37]、弦图之补[38]、置换图[27]、余图[26]、圆弧图[39]、区间序的可比图[29]、区间图，也可在多项式时间内计算出来。这种情形下，径宽比覆盖图的区间表示中所有点的最大区间数小1。
近似算法
将图的径宽近似到加常数范围内，是NP难的。[6] 已知近似率最佳的多项式时间近似算法是[math]\displaystyle{ O((\log n)^{3/2}) }[/math]。[40] 关于计算径宽的早期近似算法，见Bodlaender et al. (1992)与Guha (2000)；关于受限图类的近似计算，见Kloks & Bodlaender (1992)。
图子式
图G的子式是由G通过收缩边、移除边、移除顶点得到的另一张图。图子式有深奥的理论，其中几个重要结果涉及径宽。
排除森林
若图族F对取子式封闭（即F成员的子式还在F中），则由罗伯森–西摩定理，F的特征是在禁子式有限集X中没有任何子式。[41]例如，瓦格纳定理指出，平面图是既没有完整图[math]\displaystyle{ K_5 }[/math]也没有完全二分图[math]\displaystyle{ K_{3,\ 3} }[/math]作为子式的图。很多时候，F的性质与X的性质密切相关，此类的第一个结果由Robertson & Seymour (1983)提出，[2]将有界径宽与禁子式族中森林的存在联系起来。具体来说，若存在常数p使F中图的径宽不大于p，则称图族F具有有界径宽。那么，当且仅当F的禁子式集X至少包括一个森林时，子式闭族F具有有界的径宽。
从一个方向来看，这结果很容易证明：若X不含森林，则“无X子式图”的径宽便无界。因为这时，无X子式图将包含所有森林，特别是包括完美二叉树。而一棵[math]\displaystyle{ 2k+1 }[/math]层的完美二叉树的径宽为k，所以这时无X子式图的径宽无解。从另一方向看，若X包含n顶点森林，则无X子式图的径宽不大于[math]\displaystyle{ n-2 }[/math]。[42]
径宽有界的障碍
径宽不大于p的性质本身对取子式封闭：若G的径分解宽度不大于p，则从G中删去任何边，同一径分解仍有效，且可以从G及其径分解中删去任意顶点而不增加宽度。同样，通过合并表示收缩后边的两端点的子径，也可在收缩边时不增加分解宽度。因此，径宽至多为p的图可用排除子式的集合[math]\displaystyle{ X_p }[/math]描述。[41][43]
虽然[math]\displaystyle{ X_p }[/math]必然包括森林，但并不是说[math]\displaystyle{ X_p }[/math]中的所有图都是森林：例如，[math]\displaystyle{ X_1 }[/math]包含2张图，一个7顶点树与三角[math]\displaystyle{ K_3 }[/math]。而[math]\displaystyle{ X_p }[/math]中的树集可以精确描述：它们是[math]\displaystyle{ X_{p-1} }[/math]中三棵树通过边，连接新的根顶点与3棵小树中任意顶点而形成的树。例如，[math]\displaystyle{ X_1 }[/math]中的7顶点树就是这样由[math]\displaystyle{ X_0 }[/math]中的2顶点树（一条边）组成的。基于这种构造，可以证明[math]\displaystyle{ X_p }[/math]中的禁子式数至少为[math]\displaystyle{ (p!)^2 }[/math]。[43]已计算出2径宽图的完备禁子式集[math]\displaystyle{ X_2 }[/math]，其中包含110个图。[44]
结构理论
子式闭图族的图结构定理指出，对任意图族F，其中的图可分解为能嵌入到亏格有界曲面上的图的团和，且团和的每个分量都有有界多的顶点（apex）与涡（vortex）。这里的顶点可能与其组分中任何顶点相邻，涡是径宽有界图，粘合到某组分的亏格有界嵌入的面上。涡所嵌入面周围的顶点的循环排序必须与涡的径分解相容，即，打破循环、形成线性排序必然产生顶点分隔数有界的排序。[4]这一理论中，径宽与任意子式闭图族密切相关，具有重要的算法应用。[45]
应用
超大规模集成电路
超大规模集成电路设计中，顶点分隔问题最初是将电路分为子系统的方法，子系统边界有少量元件。[33]
Ohtsuki et al. (1979)使用区间厚度模拟VLSI一维布局所需的轨道数，此布局由网络系统相互连接的模块组成。在他们的模型中，顶点代表网，若两网都连接到同一模块，就将两顶点由边相连；也就是说，若将模块与网视作超图的结点与超边，则由它们形成的图就是超图的线图。这超图的区间表示与着色描述了沿水平轨道（一种颜色对应一条轨道）系统的网的排列，使模块可沿轨道以线性顺序排列，并连接到相应的网。区间图都是完美图[46]，表明这类最佳排列中，所需颜色数等于网图的区间完备化的团数。
门矩阵布局[47]是一种用于布尔逻辑电路的CMOS VLSI布局。当中，信号沿“线”（垂直线段）传播，而电路的每个门则由沿水平线段的一系列器件特征构成。因此，代表门的水平线段须与代表门输入输出的线路的垂直线段交叉。与Ohtsuki et al. (1979)的布局类似，通过计算以线路为顶点，以共享同一门的线对为边的图的径宽，可以找到使排列线路的垂直轨道数最小的布局。[48]这种算法方法也可为可编程逻辑阵列的折叠问题建模。[49]
图绘制
径宽在图绘制中有多个应用：
- 给定交叉数的最小图的径宽受交叉数函数的约束。[50]
- 树的顶点可画在多少条平行线上而边不交（根据对相邻顶点在线序列上摆放方式的各种自然限制），与树的径宽成正比。[51]
- 图G的k交叉h层绘图是将G的顶点放置在h条水平线上，边在其间以单调多边形路径排列，使得最多有k处交叉。具有这种绘制的图的径宽由h与k的函数约束。于是，h、k为常值时，可在线性时间内确定图是都具有k交叉h层绘制。[52]
- n顶点、径宽为p的图可嵌入3维格[math]\displaystyle{ p\times p\times n }[/math]，使得边（表为格点间的直线段）不交。于是，径宽有界图具有此种线性体积嵌入。[53]
编译器设计
高级语言的编译过程中，径宽见于重排直线代码序列（即无控制流分支或循环的代码）问题，使代码算得的所有值都可放在寄存器中，而不必溢出到主内存中。这种应用中，我们将待编译代码表为有向无环图，其中结点是代码的输入输出值。这个DAG中，结点x到结点y的边表示x值是操作了y的输入之一。此DAG的顶点的拓扑排序表示代码的有效重排，在给定排序中评估代码所需的寄存器数由排序的顶点分隔数给出。[54]
对表示寄存器数的任意定值w，可在限行时间内确定一段直线代码能否重排，以便用不多于w个寄存器求值。若拓扑排序的顶点分隔数最多为w，则所有排序中的最小顶点分隔也不会更大，于是忽略DAG方向形成的无向图的径宽不大于w。可用已知的固定参数可解算法计算径宽，若是，则可在假设w为常数的线性时间内找到无向图的径分解。找到径分解，就可用动态规划，在线性时间内找到宽w的拓扑排序。[54]
语言学
Kornai & Tuza (1992)描述了径宽在自然语言处理中的应用。句子被建模为图，顶点表示词，边表示词之间的关系。例如，若形容词修饰了名词，则图中这两个词之间就会有一条边。Kornai和Tuza认为，由于人类的短时记忆能力有限，[55]这种图的径宽一定有界（更具体地说，他们认为是6），否则人类将无法正确解析语言。
指数算法
图算法中的很多问题都可通过对径分解进行动态规划，在径宽较小的图上高效解决。[9]例如，若给定n顶点图G的顶点的线性排序，就有可能在[math]\displaystyle{ O(2^wn) }[/math]的时间内找到G的最大独立集。[30]在径宽有界图上，这种方法会产生以径宽为参数的固定参数可解算法。[48]这种结果在文献中不常见，因为已经包含在以树宽为参数的类似算法；然而，即使在基于树宽的动态规划算法中，径宽也会出现衡量算法空间复杂度的过程中。[10]
同样的动态规划方法也可用于径宽无界图，产生以指数时间解决无参图问题的算法。例如，将这种方法与立方图径宽为[math]\displaystyle{ \frac{n}{6}+o(n) }[/math]的事实相结合，可以发现在立方图中，最大支配集的构造耗时[math]\displaystyle{ O(2^{\frac{n}{6}+o(n)}) }[/math]，比以往方法更快。[30]类似方法还可改进立方图中最大割与最小支配集问题的指数时间算法，[30]及其他一些NP难优化问题的指数时间算法。[56]
注释
- ↑ Diestel & Kühn (2005).
- ↑ 2.0 2.1 2.2 2.3 Robertson & Seymour (1983).
- ↑ Bodlaender (1998).
- ↑ 4.0 4.1 Robertson & Seymour (2003).
- ↑ 5.0 5.1 Kashiwabara & Fujisawa (1979); Ohtsuki et al. (1979); Lengauer (1981); Arnborg, Corneil & Proskurowski (1987).
- ↑ 6.0 6.1 Bodlaender et al. (1992).
- ↑ 7.0 7.1 7.2 Bodlaender (1996); Bodlaender & Kloks (1996)
- ↑ 8.0 8.1 Möhring (1990); Scheffler (1990); Ellis, Sudborough & Turner (1994); Peng et al. (1998); Skodinis (2000); Skodinis (2003); Coudert, Huc & Mazauric (2012).
- ↑ 9.0 9.1 Arnborg (1985).
- ↑ 10.0 10.1 Aspvall, Proskurowski & Telle (2000).
- ↑ Bodlaender (1998), Theorem 29, p. 13.
- ↑ Kinnersley (1992); Bodlaender (1998), Theorem 51.
- ↑ Proskurowski & Telle (1999).
- ↑ Korach & Solel (1993), Lemma 3 p.99; Bodlaender (1998), Theorem 47, p. 24.
- ↑ Korach & Solel (1993), Lemma 1, p. 99; Bodlaender (1998), Theorem 49, p. 24.
- ↑ Korach & Solel (1993), Theorem 5, p. 99; Bodlaender (1998), Theorem 66, p. 30. Scheffler (1992)为n顶点森林的径宽提供了更紧的上界：[math]\displaystyle{ \log_3(2n+1) }[/math]。
- ↑ Korach & Solel (1993), Theorem 6, p. 100; Bodlaender (1998), Corollary 24, p.10.
- ↑ Gurski & Wanke (2007).
- ↑ Golovach (1993).
- ↑ Bodlaender (1998), Corollary 23, p. 10.
- ↑ Bodlaender (1998), Theorem 20, p. 9.
- ↑ Alon, Seymour & Thomas (1990).
- ↑ Bodlaender & Fomin (2002); Coudert, Huc & Sereni (2007).
- ↑ Fomin & Thilikos (2007); Amini, Huc & Pérennes (2009).
- ↑ Fomin (2003).
- ↑ 26.0 26.1 Bodlaender & Möhring (1990).
- ↑ 27.0 27.1 Bodlaender, Kloks & Kratsch (1993).
- ↑ 28.0 28.1 Habib & Möhring (1994).
- ↑ 29.0 29.1 Garbe (1995).
- ↑ 30.0 30.1 30.2 30.3 Fomin & Høie (2006).
- ↑ Fomin et al. (2008).
- ↑ Downey & Fellows (1999), p.12.
- ↑ 33.0 33.1 33.2 33.3 Monien & Sudborough (1988).
- ↑ Gustedt (1993).
- ↑ Kloks, Kratsch & Müller (1995). 弦多米诺是顶点都属于至多2个最大团的弦图。
- ↑ 36.0 36.1 Kloks et al. (1993).
- ↑ Kloks & Bodlaender (1992); Gustedt (1993).
- ↑ Garbe (1995)将此成果归功于Ton Kloks的博士论文（1993）；Garbe对区间序的可比图的多项式时间算法推广了结果，而弦图属于此类可比图。
- ↑ Suchan & Todinca (2007).
- ↑ Feige, Hajiaghayi & Lee (2005).
- ↑ 41.0 41.1 Robertson & Seymour (2004).
- ↑ Bienstock et al. (1991); Diestel (1995); Cattell, Dinneen & Fellows (1996).
- ↑ 43.0 43.1 Kinnersley (1992); Takahashi, Ueno & Kajitani (1994); Bodlaender (1998), p. 8.
- ↑ Kinnersley & Langston (1994).
- ↑ Demaine, Hajiaghayi & Kawarabayashi (2005).
- ↑ Berge (1967).
- ↑ Lopez & Law (1980).
- ↑ 48.0 48.1 Fellows & Langston (1989).
- ↑ Möhring (1990); Ferreira & Song (1992).
- ↑ Hliněny (2003).
- ↑ Suderman (2004).
- ↑ Dujmović et al. (2008).
- ↑ Dujmović, Morin & Wood (2003).
- ↑ 54.0 54.1 Bodlaender, Gustedt & Telle (1998).
- ↑ Miller (1956).
- ↑ Kneis et al. (2005); Björklund & Husfeldt (2008).
参考文献
- Alon, Noga; Seymour, Paul; Thomas, Robin (1990), "A separator theorem for graphs with an excluded minor and its applications", Proc. 22nd ACM Symp. on Theory of Computing (STOC 1990), pp. 293–299, doi:10.1145/100216.100254, ISBN 0897913612, S2CID 17521329.
- Amini, Omid; Huc, Florian; Pérennes, Stéphane (2009), "On the path-width of planar graphs", SIAM Journal on Discrete Mathematics, 23 (3): 1311–1316, doi:10.1137/060670146.
- Arnborg, Stefan (1985), "Efficient algorithms for combinatorial problems on graphs with bounded decomposability – A survey", BIT, 25 (1): 2–23, doi:10.1007/BF01934985, S2CID 122263659.
- Arnborg, Stefan; Corneil, Derek G.; Proskurowski, Andrzej (1987), "Complexity of finding embeddings in a k-tree", SIAM Journal on Algebraic and Discrete Methods, 8 (2): 277–284, doi:10.1137/0608024.
- Aspvall, Bengt; Proskurowski, Andrzej; Telle, Jan Arne (2000), "Memory requirements for table computations in partial k-tree algorithms", Algorithmica, 27 (3): 382–394, doi:10.1007/s004530010025, S2CID 9690525.
- Berge, Claude (1967), "Some classes of perfect graphs", Graph Theory and Theoretical Physics, New York: Academic Press, pp. 155–165.
- Bienstock, Dan; Robertson, Neil; Seymour, Paul; Thomas, Robin (1991), "Quickly excluding a forest", Journal of Combinatorial Theory, Series B, 52 (2): 274–283, doi:10.1016/0095-8956(91)90068-U.
- Björklund, Andreas; Husfeldt, Thore (2008), "Exact algorithms for exact satisfiability and number of perfect matchings", Algorithmica, 52 (2): 226–249, doi:10.1007/s00453-007-9149-8, S2CID 37693881.
- Bodlaender, Hans L. (1994), "A tourist guide through treewidth", in Dassow, Jürgen; Kelemenová, Alisa (eds.), Developments in Theoretical Computer Science (Proc. 7th International Meeting of Young Computer Scientists, Smolenice, 16–20 November 1992), Topics in Computer Mathematics, vol. 6, Gordon and Breach, pp. 1–20.
- Bodlaender, Hans L. (1994a). "A tourist guide through treewidth". Acta Cybernetica. 11: 1–2.
- Bodlaender, Hans L. (1996), "A linear-time algorithm for finding tree-decompositions of small treewidth", SIAM Journal on Computing, 25 (6): 1305–1317, doi:10.1137/S0097539793251219, hdl:1874/16670.
- Bodlaender, Hans L. (1998), "A partial k-arboretum of graphs with bounded treewidth", Theoretical Computer Science, 209 (1–2): 1–45, doi:10.1016/S0304-3975(97)00228-4.
- Bodlaender, Hans L.; Fomin, Fedor V. (2002), "Approximation of pathwidth of outerplanar graphs", Journal of Algorithms, 43 (2): 190–200, doi:10.1016/S0196-6774(02)00001-9.
- Bodlaender, Hans L.; Gilbert, John R.; Hafsteinsson, Hjálmtýr; Kloks, Ton (1992), "Approximating treewidth, pathwidth, and minimum elimination tree height", Graph-Theoretic Concepts in Computer Science, Lecture Notes in Computer Science, vol. 570, pp. 1–12, doi:10.1007/3-540-55121-2_1, hdl:1874/17927, ISBN 978-3-540-55121-8.
- Bodlaender, Hans L.; Gustedt, Jens; Telle, Jan Arne (1998), "Linear-time register allocation for a fixed number of registers", Proc. 9th ACM–SIAM Symposium on Discrete Algorithms (SODA '98) (PDF), pp. 574–583, archived from the original (PDF) on 2023-01-30, retrieved 2024-01-31
{{citation}}: Unknown parameter|dead-url=ignored (help). - Bodlaender, Hans L.; Kloks, Ton (1996), "Efficient and constructive algorithms for the pathwidth and treewidth of graphs", Journal of Algorithms, 21 (2): 358–402, doi:10.1006/jagm.1996.0049, hdl:1874/16538.
- Bodlaender, Hans L.; Kloks, Ton; Kratsch, Dieter (1993), "Treewidth and pathwidth of permutation graphs", Proc. 20th International Colloquium on Automata, Languages and Programming (ICALP 1993), Lecture Notes in Computer Science, vol. 700, Springer-Verlag, pp. 114–125, doi:10.1007/3-540-56939-1_66, hdl:1874/16657, ISBN 978-3-540-56939-8.
- Bodlaender, Hans L.; Möhring, Rolf H. (1990), "The pathwidth and treewidth of cographs", Proc. 2nd Scandinavian Workshop on Algorithm Theory, Lecture Notes in Computer Science, vol. 447, Springer-Verlag, pp. 301–309, doi:10.1007/3-540-52846-6_99, hdl:1874/16625, ISBN 978-3-540-52846-3.
- Cattell, Kevin; Dinneen, Michael J.; Fellows, Michael R. (1996), "A simple linear-time algorithm for finding path-decompositions of small width", Information Processing Letters, 57 (4): 197–203, arXiv:math/9410211, doi:10.1016/0020-0190(95)00190-5, S2CID 2442557.
- Coudert, David; Huc, Florian; Mazauric, Dorian (2012), "A Distributed Algorithm for Computing the Node Search Number in Trees" (PDF), Algorithmica, 63 (1): 158–190, doi:10.1007/s00453-011-9524-3, archived from the original (PDF) on 2022-01-03, retrieved 2024-01-31
{{citation}}: Unknown parameter|dead-url=ignored (help). - Coudert, David; Huc, Florian; Sereni, Jean-Sébastien (2007), "Pathwidth of outerplanar graphs" (PDF), Journal of Graph Theory, 55 (1): 27–41, doi:10.1002/jgt.20218, archived from the original (PDF) on 2022-01-03, retrieved 2024-01-31
{{citation}}: Unknown parameter|dead-url=ignored (help). - Diestel, Reinhard (1995), "Graph Minors I: a short proof of the path-width theorem", Combinatorics, Probability and Computing, 4 (1): 27–30, doi:10.1017/S0963548300001450.
- Diestel, Reinhard; Kühn, Daniela (2005), "Graph minor hierarchies", Discrete Applied Mathematics, 145 (2): 167–182, doi:10.1016/j.dam.2004.01.010.
- Demaine, Erik D.; Hajiaghayi, MohammadTaghi; Kawarabayashi, Ken-ichi (2005), "Algorithmic graph minor theory: decomposition, approximation, and coloring", Proc. 46th IEEE Symposium on Foundations of Computer Science (FOCS 2005), pp. 637–646, doi:10.1109/SFCS.2005.14, ISBN 0-7695-2468-0, S2CID 13238254.
- Downey, Rod G.; Fellows, Michael R. (1999), Parameterized Complexity, Springer-Verlag, ISBN 0-387-94883-X.
- Dujmović, V.; Fellows, M.R.; Kitching, M.; Liotta, G.; McCartin, C.; Nishimura, N.; Ragde, P.; Rosamond, F.; Whitesides, S.; Wood, David R. (2008), "On the parameterized complexity of layered graph drawing", Algorithmica, 52 (2): 267–292, doi:10.1007/s00453-007-9151-1, S2CID 2298634.
- Dujmović, Vida; Morin, Pat; Wood, David R. (2003), "Path-width and three-dimensional straight-line grid drawings of graphs" (PDF), Proc. 10th International Symposium on Graph Drawing (GD 2002), Lecture Notes in Computer Science, vol. 2528, Springer-Verlag, pp. 42–53, archived from the original (PDF) on 2012-03-04, retrieved 2024-01-31
{{citation}}: Unknown parameter|dead-url=ignored (help). - Ellis, J. A.; Sudborough, I. H.; Turner, J. S. (1983), "Graph separation and search number", Proc. 1983 Allerton Conf. on Communication, Control, and Computing. As cited by Monien & Sudborough (1988).
- Ellis, J. A.; Sudborough, I. H.; Turner, J. S. (1994), "The vertex separation and search number of a tree", Information and Computation, 113 (1): 50–79, doi:10.1006/inco.1994.1064.
- Feige, Uriel; Hajiaghayi, Mohammadtaghi; Lee, James R. (2005), "Improved approximation algorithms for minimum-weight vertex separators", Proc. 37th ACM Symposium on Theory of Computing (STOC 2005), pp. 563–572, doi:10.1145/1060590.1060674, ISBN 1581139608, S2CID 14097859.
- Fellows, Michael R.; Langston, Michael A. (1989), "On search decision and the efficiency of polynomial-time algorithms", Proc. 21st ACM Symposium on Theory of Computing, pp. 501–512, doi:10.1145/73007.73055, ISBN 0897913078, S2CID 1854173.
- Ferreira, Afonso G.; Song, Siang W. (1992), "Achieving optimality for gate matrix layout and PLA folding: a graph theoretic approach", Proc. 1st Latin American Symposium on Theoretical Informatics (LATIN '92), Lecture Notes in Computer Science, vol. 583, Springer-Verlag, pp. 139–153, doi:10.1007/BFb0023825, hdl:10068/43314, ISBN 3-540-55284-7.
- de Fluiter, Babette (1997), Algorithms for Graphs of Small Treewidth (PDF), Ph.D. thesis, Utrecht University, ISBN 90-393-1528-0, archived from the original (PDF) on 2011-07-24, retrieved 2010-05-06.
- Fomin, Fedor V. (2003), "Pathwidth of planar and line graphs", Graphs and Combinatorics, 19 (1): 91–99, doi:10.1007/s00373-002-0490-z, S2CID 43123449.
- Fomin, Fedor V.; Høie, Kjartan (2006), "Pathwidth of cubic graphs and exact algorithms", Information Processing Letters, 97 (5): 191–196, doi:10.1016/j.ipl.2005.10.012.
- Fomin, Fedor V.; Kratsch, Dieter; Todinca, Ioan; Villanger, Yngve (2008), "Exact algorithms for treewidth and minimum fill-in", SIAM Journal on Computing, 38 (3): 1058–1079, doi:10.1137/050643350, hdl:1956/1151.
- Fomin, Fedor V.; Thilikos, Dimitrios M. (2007), "On self duality of pathwidth in polyhedral graph embeddings", Journal of Graph Theory, 55 (1): 42–54, doi:10.1002/jgt.20219.
- Garbe, Renate (1995), "Tree-width and path-width of comparability graphs of interval orders", Proc. 20th International Workshop Graph-Theoretic Concepts in Computer Science (WG'94), Lecture Notes in Computer Science, vol. 903, Springer-Verlag, pp. 26–37, doi:10.1007/3-540-59071-4_35, ISBN 978-3-540-59071-2.
- Golovach, P. A. (1993), "The cutwidth of a graph and the vertex separation number of the line graph", Discrete Mathematics and Applications, 3 (5): 517–522, doi:10.1515/dma.1993.3.5.517, S2CID 120745961.
- Guha, Sudipto (2000), "Nested graph dissection and approximation algorithms", Proc. 41st IEEE Symposium on Foundations of Computer Science (FOCS 2000), p. 126, doi:10.1109/SFCS.2000.892072, ISBN 0-7695-0850-2, S2CID 9854056.
- Gurski, Frank; Wanke, Egon (2007), "Line graphs of bounded clique-width", Discrete Mathematics, 307 (22): 2734–2754, doi:10.1016/j.disc.2007.01.020.
- Gustedt, Jens (1993), "On the pathwidth of chordal graphs", Discrete Applied Mathematics, 45 (3): 233–248, doi:10.1016/0166-218X(93)90012-D.
- Habib, Michel; Möhring, Rolf H. (1994), "Treewidth of cocomparability graphs and a new order-theoretic parameter", Order, 11 (1): 47–60, doi:10.1007/BF01462229, S2CID 2648030.
- Hliněny, Petr (2003), "Crossing-number critical graphs have bounded path-width", Journal of Combinatorial Theory, Series B, 88 (2): 347–367, doi:10.1016/S0095-8956(03)00037-6.
- Kashiwabara, T.; Fujisawa, T. (1979), "NP-completeness of the problem of finding a minimum-clique-number interval graph containing a given graph as a subgraph", Proc. International Symposium on Circuits and Systems, pp. 657–660.
- Kinnersley, Nancy G. (1992), "The vertex separation number of a graph equals its path-width", Information Processing Letters, 42 (6): 345–350, doi:10.1016/0020-0190(92)90234-M.
- Kinnersley, Nancy G.; Langston, Michael A. (1994), "Obstruction set isolation for the gate matrix layout problem", Discrete Applied Mathematics, 54 (2–3): 169–213, doi:10.1016/0166-218X(94)90021-3.
- Kirousis, Lefteris M.; Papadimitriou, Christos H. (1985), "Interval graphs and searching" (PDF), Discrete Mathematics, 55 (2): 181–184, doi:10.1016/0012-365X(85)90046-9, archived from the original (PDF) on 2011-07-21.
- Kloks, Ton; Bodlaender, Hans L. (1992), "Approximating treewidth and pathwidth of some classes of perfect graphs", Proc. 3rd International Symposium on Algorithms and Computation (ISAAC'92), Lecture Notes in Computer Science, vol. 650, Springer-Verlag, pp. 116–125, doi:10.1007/3-540-56279-6_64, hdl:1874/16672, ISBN 978-3-540-56279-5.
- Kloks, T.; Bodlaender, H.; Müller, H.; Kratsch, D. (1993), "Computing treewidth and minimum fill-in: all you need are the minimal separators", Proc. 1st European Symposium on Algorithms (ESA'93) (Lecture Notes in Computer Science), vol. 726, Springer-Verlag, pp. 260–271, doi:10.1007/3-540-57273-2_61.
- Kloks, Ton; Kratsch, Dieter; Müller, H. (1995), "Dominoes", Proc. 20th International Workshop Graph-Theoretic Concepts in Computer Science (WG'94), Lecture Notes in Computer Science, vol. 903, Springer-Verlag, pp. 106–120, doi:10.1007/3-540-59071-4_41, ISBN 978-3-540-59071-2.
- Kneis, Joachim; Mölle, Daniel; Richter, Stefan; Rossmanith, Peter (2005), "Algorithms based on the treewidth of sparse graphs", Proc. 31st International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2005), Lecture Notes in Computer Science, vol. 3787, Springer-Verlag, pp. 385–396, doi:10.1007/11604686_34, ISBN 978-3-540-31000-6.
- Korach, Ephraim; Solel, Nir (1993), "Tree-width, path-width, and cutwidth", Discrete Applied Mathematics, 43 (1): 97–101, doi:10.1016/0166-218X(93)90171-J.
- Kornai, András; Tuza, Zsolt (1992), "Narrowness, path-width, and their application in natural language processing", Discrete Applied Mathematics, 36 (1): 87–92, doi:10.1016/0166-218X(92)90208-R.
- Lengauer, Thomas (1981), "Black-white pebbles and graph separation", Acta Informatica, 16 (4): 465–475, doi:10.1007/BF00264496, S2CID 19415148.
- Lopez, Alexander D.; Law, Hung-Fai S. (1980), "A dense gate matrix layout method for MOS VLSI", IEEE Transactions on Electron Devices, 27 (8): 1671–1675, Bibcode:1980ITED...27.1671L, doi:10.1109/T-ED.1980.20086, S2CID 64469353, Also in the joint issue, IEEE Journal of Solid-State Circuits 15 (4): 736–740, 1980.
- Miller, George A. (1956), "The Magical Number Seven, Plus or Minus Two", Psychological Review, 63 (2): 81–97, doi:10.1037/h0043158, hdl:11858/00-001M-0000-002C-4646-B, PMID 13310704, archived from the original on 2008-05-30, retrieved 2024-01-31
{{citation}}: Unknown parameter|dead-url=ignored (help). - Möhring, Rolf H. (1990), "Graph problems related to gate matrix layout and PLA folding", in Tinhofer, G.; Mayr, E.; Noltemeier, H.; et al. (eds.), Computational Graph Theory, Computing Supplementum, vol. 7, Springer-Verlag, pp. 17–51, ISBN 3-211-82177-5.
- Monien, B.; Sudborough, I. H. (1988), "Min cut is NP-complete for edge weighted trees", Theoretical Computer Science, 58 (1–3): 209–229, doi:10.1016/0304-3975(88)90028-X.
- Ohtsuki, Tatsuo; Mori, Hajimu; Kuh, Ernest S.; Kashiwabara, Toshinobu; Fujisawa, Toshio (1979), "One-dimensional logic gate assignment and interval graphs", IEEE Transactions on Circuits and Systems, 26 (9): 675–684, doi:10.1109/TCS.1979.1084695.
- Peng, Sheng-Lung; Ho, Chin-Wen; Hsu, Tsan-sheng; Ko, Ming-Tat; Tang, Chuan Yi (1998), "A linear-time algorithm for constructing an optimal node-search strategy of a tree", Proc. 4th Int. Conf. Computing and Combinatorics (COCOON'98), Lecture Notes in Computer Science, vol. 1449, Springer-Verlag, pp. 197–205https://en.wikipedia.org/wiki/Defekte_Weblinks?dwl={{{url}}} Seite nicht mehr abrufbar], Suche in Webarchiven: Kategorie:Wikipedia:Weblink offline (andere Namensräume)[http://timetravel.mementoweb.org/list/2010/Kategorie:Wikipedia:Vorlagenfehler/Vorlage:Toter Link/URL_fehlt 模板:Cbignore.
- Proskurowski, Andrzej; Telle, Jan Arne (1999), "Classes of graphs with restricted interval models" (PDF), Discrete Mathematics and Theoretical Computer Science, 3: 167–176, archived from the original (PDF) on 2024-01-31, retrieved 2024-01-31
{{citation}}: Unknown parameter|dead-url=ignored (help). - Robertson, Neil; Seymour, Paul (1983), "Graph minors. I. Excluding a forest", Journal of Combinatorial Theory, Series B, 35 (1): 39–61, doi:10.1016/0095-8956(83)90079-5.
- Robertson, Neil; Seymour, Paul (2003), "Graph minors. XVI. Excluding a non-planar graph", Journal of Combinatorial Theory, Series B, 89 (1): 43–76, doi:10.1016/S0095-8956(03)00042-X.
- Robertson, Neil; Seymour, Paul D. (2004), "Graph Minors. XX. Wagner's conjecture", Journal of Combinatorial Theory, Series B, 92 (2): 325–357, doi:10.1016/j.jctb.2004.08.001.
- Scheffler, Petra (1990), "A linear algorithm for the pathwidth of trees", in Bodendiek, R.; Henn, R. (eds.), Topics in Combinatorics and Graph Theory, Physica-Verlag, pp. 613–620.
- Scheffler, Petra (1992), "Optimal embedding of a tree into an interval graph in linear time", in Nešetřil, Jaroslav; Fiedler, Miroslav (eds.), Fourth Czechoslovakian Symposium on Combinatorics, Graphs and Complexity, Elsevier.
- Skodinis, Konstantin (2000), "Computing optimal linear layouts of trees in linear time", Proc. 8th European Symposium on Algorithms (ESA 2000), Lecture Notes in Computer Science, vol. 1879, Springer-Verlag, pp. 403–414, doi:10.1007/3-540-45253-2_37, ISBN 978-3-540-41004-1.
- Skodinis, Konstantin (2003), "Construction of linear tree-layouts which are optimal with respect to vertex separation in linear time", Journal of Algorithms, 47 (1): 40–59, doi:10.1016/S0196-6774(02)00225-0.
- Suchan, Karol; Todinca, Ioan (2007), "Pathwidth of circular-arc graphs", Proc. 33rd International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2007), Lecture Notes in Computer Science, vol. 4769, Springer-Verlag, pp. 258–269, doi:10.1007/978-3-540-74839-7_25.
- Suderman, Matthew (2004), "Pathwidth and layered drawings of trees" (PDF), International Journal of Computational Geometry and Applications, 14 (3): 203–225, doi:10.1142/S0218195904001433, archived from the original (PDF) on 2003-05-03.
- Takahashi, Atsushi; Ueno, Shuichi; Kajitani, Yoji (1994), "Minimal acyclic forbidden minors for the family of graphs with bounded path-width", Discrete Mathematics, 127 (1–3): 293–304, doi:10.1016/0012-365X(94)90092-2.