91
个编辑
更改
跳到导航
跳到搜索
第61行：
第61行： − {{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"/>+
→特殊图类
===特殊图类===
===特殊图类===
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。
不过，对于树与森林，径宽可在线性时间内算得。<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。