Computing the bandwidth of interval graphs
Computing the bandwidth of interval graphs
复制标题
计算区间图的带宽
DOI：
10.1137/0403033
复制
发表时间：
1990
影响因子：
0.8
通讯作者：
S. Ajoodani
中科院分区：
文献类型：
--
作者：
G. Khosrovshahi;S. Ajoodani
在这篇文章中，一个$O（|V|本文给出了一个判定上的区间图是否为区间图的算法|V| $ vertices的带宽小于或等于给定的整数k。虽然该算法不是第一个解决这个问题的算法，但它确实承认其正确性的证明比Kratsch（Information and Computation，74（1987），pp. 140-158）。
In this note, an $O ( | V |k )$ algorithm is described for determining whether an interval graph on $| V |$ vertices has a bandwidth less than or equal to a given integer k. While the algorithm is not the first to resolve this problem, it does admit a shorter proof of its correctness than a previous algorithm of the same complexity due to Kratsch (Information and Computation, 74 (1987), pp. 140–158).