English

运筹学学报 ›› 2020, Vol. 24 ›› Issue (4): 153-158.doi: 10.15960/j.cnki.issn.1007-6093.2020.04.014

• • 上一篇    

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

林浩1,*, 林澜2   

  1. 1. 河南工业大学理学院, 郑州 450001;
    2. 同济大学电子与信息工程学院, 上海 200092
  • 收稿日期:2018-11-19 发布日期:2020-11-18
  • 通讯作者: 林浩 E-mail:linhao@haut.edu.cn
  • 基金资助:
    国家自然科学基金（Nos.11571323，61373106）

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

LIN Hao1,*, LIN Lan2   

  1. 1. School of Science, Henan University of Technology, Zhengzhou 450001, China;
    2. School of Electronics and Information Engineering, Tongji University, Shanghai 200092, China
  • Received:2018-11-19 Published:2020-11-18

PDF

87

摘要： 图G的最小伸展支撑树问题是寻求图G的支撑树T，使得相邻两顶点在T中的最大距离达到最小。这个最小值称为图G的树展，记作σ（G）。此问题已被证明为NP-困难的，对若干特殊图类亦已得到上界估计。例如对区间图已知σ（G）≤ 3，对区间图得到σ（G）=k，k=1，2，3的完整刻画。

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

Abstract: 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 adjacent 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.

Key words: spanning tree optimization, tree-stretch, characterization, interval graph

中图分类号: