树的补图的区间图完全化问题

摘要：

一个图G的区间图完全化问题包含两类子问题:侧廓问题和路宽问题,分别表示为P(G)和PW(G),其中侧廓问题是寻求G的一个边数最小的区间超图;路宽问题是寻求G的一个团数最小的区间超图.这两类子问题分别在数值代数、VLSI-设计和算法图论等学科领域中有重要的应用.对一般图来说,两类子问题都是NP-完全问题;但是对一些特殊图类来说,它们在多项式时间内可解.本文给出了树T的补图的具体侧廓和路宽值.

关键词：区间图、侧廓、路宽、树、树的补图

所属期刊栏目：22

分类号：O157.5(代数、数论、组合理论)

资助基金：the Natural Science Foundation of Henan Province082300460190

在线出版日期：2009-04-15（万方平台首次上网日期，不代表论文的发表时间）

页数：共8页

页码：48-55