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

• 作者: 张振坤
• 来源期刊: 应用数学
• 学科: 数学
• 关键词: 区间图 侧廓 路宽 树 树的补图
• 年，卷（期）: 2009,（1）
• 页码范围: 48-55
• 页数: 8页
• 分类号: O157.5
• 字数: 3356字
• 语种: 中文

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	张振坤	黄淮学院数学系	22	22	3.0	3.0