区间图最小伸展支撑树问题的最优性刻画  

Optimality characterization of the minimum stretch spanning tree problem for interval graphs

作　　者：林浩[1] 林澜[2] LIN Hao;LIN Lan(School of Science,Henan University of Technology,Zhengzhou 450001,China;School of Electronics and Information Engineering,Tongji University,Shanghai 200092,China)

机构地区：[1]河南工业大学理学院,郑州450001 [2]同济大学电子与信息工程学院,上海200092

出　　处：《运筹学学报》2020年第4期153-158,共6页Operations Research Transactions

基　　金：国家自然科学基金(Nos.11571323,61373106)。

摘　　要：图G的最小伸展支撑树问题是寻求图G的支撑树T,使得相邻两顶点在T中的最大距离达到最小。这个最小值称为图G的树展,记作σ(G)。此问题已被证明为NP-困难的,对若干特殊图类亦已得到上界估计。例如对区间图已知σ(G)≤3,对区间图得到σ(G)=k,k=1,2,3的完整刻画。The minimum stretch spanning tree problem for a graph G is to find a spanning tree T of G such that the maximum distance in T between two adj acent vertices is minimized.This minimum value is called the tree-stretch of G,denotedσ(G).The problem has been proved NP-hard and several upper bounds have been obtained for special graph classes.For example,σ(G)≤3 is known for interval graphs.This paper presents a characterization of interval graphs withσ(G)=k for k=1,2,3.

关 键 词：支撑树最优化 树展 刻画 区间图 

分 类 号：O221.7[理学—运筹学与控制论]