Approximating the Bandwidth for Asteroidal Triple-Free Graphs
Approximating the Bandwidth for Asteroidal Triple-Free Graphs
复制标题
近似小行星三自由图的带宽
DOI：
10.1006/jagm.1998.0997
复制
发表时间：
1995
期刊：
影响因子：
--
通讯作者：
H. Müller
中科院分区：
文献类型：
--
作者：
T. Kloks;D. Kratsch;H. Müller
我们表明，有一个O（n3）的算法来近似的AT-自由图的带宽与最坏情况下的性能比2。或者，在近似因子的成本，我们也可以得到一个O（e+n log n）的算法来近似的AT-自由图的带宽在一个因素4。对于特殊情况下的排列图和梯形图，我们得到O（n log n）的算法，最坏情况下的性能比2。对于协可比图，我们得到了一个O（n2）的算法，最坏情况下的性能比3。
We show that there is an O(n3) algorithm to approximate the bandwidth of an AT-free graph with worst case performance ratio 2. Alternatively, at the cost of the approximation factor, we can also obtain an O(e+n log n) algorithm to approximate the bandwidth of an AT-free graph within a factor 4. For the special cases of permutation graphs and trapezoid graphs we obtain O(n log n) algorithms with worst case performance ratio 2. For cocomparability graphs we obtain an O(n2) algorithm with worst case performance ratio 3.