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