树的补图的区间图完全化问题(英文)

作     者：张振坤 ZHANG Zhen-kun

作者机构：黄淮学院数学系河南驻马店463000 

基　　金：Supported by the Natural Science Foundation of Henan Province(082300460190) 

出 版 物：《应用数学》 (Mathematica Applicata)

年 卷 期：2009年第22卷第1期

页      码：48-55页

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

主 题 词：区间图 侧廓 路宽 树 树的补图 

学科分类：07[理学] 070104[070104] 0701[理学-数学类] 

核心收录：

馆 藏 号：203154177...