Bandwidth of Split and Circular Permutation Graphs
Bandwidth of Split and Circular Permutation Graphs
复制标题
分裂和循环排列图的带宽
DOI：
10.1007/3-540-40064-8_23
复制
发表时间：
2000
期刊：
影响因子：
--
通讯作者：
H. Müller
中科院分区：
文献类型：
--
作者：
T. Kloks;D. Kratsch;Y. L. Borgne;H. Müller
研究了一些特殊图类图上的带宽最小化问题，得到了以下结果。当仅限于分割图时，该问题仍然是 NP 完全问题。有一种线性时间算法可以计算称为刺猬的分裂图子类的确切带宽。有一种有效的算法可以将圆形排列图的带宽近似为四倍。
The BANDWIDTH minimization problem on graphs of some special graph classes is studied and the following results are obtained. The problem remains NP-complete when restricted to splitgraphs. There is a linear time algorithm to compute the exact bandwidth of a subclass of splitgraphs called hedgehogs. There is an efficient algorithm to approximate the bandwidth of circular permutation graphs within a factor of four.