| 树的补图的区间图完全化问题 |
| |
| 引用本文： | 张振坤.树的补图的区间图完全化问题[J].应用数学,2009,22(1). |
| |
| 作者姓名： | 张振坤 |
| |
| 作者单位： | 黄淮学院数学系,河南,驻马店,463000 |
| |
| 摘 要： | 一个图G的区间图完全化问题包含两类子问题:侧廓问题和路宽问题,分别表示为P(G)和PW(G),其中侧廓问题是寻求G的一个边数最小的区间超图;路宽问题是寻求G的一个团数最小的区间超图.这两类子问题分别在数值代数、VLSI-设计和算法图论等学科领域中有重要的应用.对一般图来说,两类子问题都是NP-完全问题;但是对一些特殊图类来说,它们在多项式时间内可解.本文给出了树T的补图的具体侧廓和路宽值.
|
| 关 键 词： | 区间图 侧廓 路宽 树 树的补图 |
The Interval Graph Completion Problem of the Complements of Trees |
| |
| ZHANG Zhen-kun.The Interval Graph Completion Problem of the Complements of Trees[J].Mathematica Applicata,2009,22(1). |
| |
| Authors: | ZHANG Zhen-kun |
| |
| Abstract: | The interval graph completion problem of a graph G includes two subproblems:the profile problem and pathwidth problem,denoted as P(G) and PW(G) respectively,where the profile problem is to find an interval supergraph with the smallest possible number of edges;the pathwidth problem is to find an interval supergraph with the smallest possible cliquesize.These two subproblems have important applications to numerical algebra,VLSI-layout and algorithm graph theory respectively;and they are known to be NP-complete for general graphps.Some classes of special graphs have been investigated in the literatures.In this paper the concrete profile and pathwidth values of the complement graph of any tree T are given. |
| |
| Keywords: | The interval graph Profile Pathwidth Tree The complement of tree |
| 本文献已被 维普 万方数据 等数据库收录！ |
|
