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

The Interval Graph Completion Problem of the Complements of Trees

作　　者：张振坤[1] 

机构地区：[1]黄淮学院数学系,河南驻马店463000

出　　处：《应用数学》2009年第1期48-55,共8页Mathematica Applicata

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

摘　　要：一个图G的区间图完全化问题包含两类子问题:侧廓问题和路宽问题,分别表示为P( G)和PW( G) ,其中侧廓问题是寻求G的一个边数最小的区间超图;路宽问题是寻求G的一个团数最小的区间超图.这两类子问题分别在数值代数、VLSI-设计和算法图论等学科领域中有重要的应用.对一般图来说,两类子问题都是NP-完全问题;但是对一些特殊图类来说,它们在多项式时间内可解.本文给出了树T的补图T-的具体侧廓和路宽值.The interval graph completion problem of a graph G includes two subproblems., the pro- file 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, VLSl-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 T of any tree T are given.

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

分 类 号：O157.5[理学—数学]