中文

Operations Research Transactions ›› 2020, Vol. 24 ›› Issue (4): 153-158.doi: 10.15960/j.cnki.issn.1007-6093.2020.04.014

Previous Articles    

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

144

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

CLC Number: