Bandwidth of bipartite permutation graphs in polynomial time
Bandwidth of bipartite permutation graphs in polynomial time
复制标题
多项式时间内二分置换图的带宽
DOI：
10.1016/j.jda.2008.11.001
复制
发表时间：
2008
期刊：
影响因子：
--
通讯作者：
D. Meister
中科院分区：
文献类型：
--
作者：
P. Heggernes;D. Kratsch;D. Meister
我们给出了第一个计算二部置换图带宽的多项式时间算法。带宽是一个 NP 完全图布局问题，即使在小型图类上也因其困难而臭名昭著。例如，对于毛发长度最多为 3 的毛毛虫（树木的一个非常有限的子类），它仍然是 NP 完全的。由于在常数因子保证下近似一般图的带宽是 NP 困难的，因此设计用于计算带宽的近似算法受到了很多关注。即使对于受限类的近似，这个问题也被认为很重要，在这个方向上有几个显着的结果。在我们的工作之前，用于精确计算带宽的多项式时间算法仅适用于头发长度最多为 2 的毛毛虫、链图、cographs 以及最有趣的区间图。
We give the first polynomial-time algorithm that computes the bandwidth of bipartite permutation graphs. Bandwidth is an NP-complete graph layout problem that is notorious for its difficulty even on small graph classes. For example, it remains NP-complete on caterpillars of hair length at most 3, a very restricted subclass of trees. Much attention has been given to designing approximation algorithms for computing the bandwidth, as it is NP-hard to approximate the bandwidth of general graphs with a constant factor guarantee. The problem is considered important even for approximation on restricted classes, with several distinguished results in this direction. Prior to our work, polynomial-time algorithms for exact computation of bandwidth were known only for caterpillars of hair length at most 2, chain graphs, cographs, and most interestingly, interval graphs.