中文

Operations Research Transactions >

2020 , Vol. 24 >Issue 4: 153 - 158

DOI: https://doi.org/10.15960/j.cnki.issn.1007-6093.2020.04.014

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

Expand
  • 1. School of Science, Henan University of Technology, Zhengzhou 450001, China;
    2. School of Electronics and Information Engineering, Tongji University, Shanghai 200092, China

Received date: 2018-11-19

  Online published: 2020-11-18

Fold

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

Cite this article

LIN Hao, LIN Lan . Optimality characterization of the minimum stretch spanning tree problem for interval graphs[J]. Operations Research Transactions, 2020 , 24(4) : 153 -158 . DOI: 10.15960/j.cnki.issn.1007-6093.2020.04.014

References

[1] Galbiati G. On finding cycle bases and fundamental cycle bases with a shortest maximal cycles[J]. Information Processing Letters, 2003, 88:155-159.
[2] Peleg D, Ullman J D. An optimal synchroniser for the hypercube[J]. SIAM Journal on Computing, 1989, 18(4):740-747.
[3] Liebchen C, Wünsch G. The zoo of tree spanner problems[J]. Discrete Applied Mathematics, 2008, 156:569-587.
[4] Cai L, Corneil D G. Tree spanners[J]. SIAM Journal on Discrete Mathematics, 1995, 8:359-387.
[5] Brandstädt A, Dragan F F, Le H O, et al. Tree spanners on chordal graphs:complexity and algorithms[J]. Theoretical Computer Science, 2004, 310:329-354.
[6] Brandstädt A, Dragan F F, Le H O, et al. Tree spanners for bipartite graphs and probe interval graphs[J]. Algorithmica, 2007, 47:27-51.
[7] Le H O, Le V B. Optimal tree 3-spanners in directed path graphs[J]. Networks, 1999, 34:81-87.
[8] Madanlal M S, Venkatesan G, Rangan C P. Tree 3-spanners on interval, permutation and regular bipartite graphs[J]. Information Processing Letters, 1996, 59:97-102.
[9] Bondy J A, Murty U S R. Graph Theory[M]. Berlin:Springer-Verlag, 2008.
[10] Golumbic M C. Algorithmic Graph Theory and Perfect Graphs[M]. New York:Academic Press, 1980.
[11] Hassin R, Tamir A. On the minimum diameter spanning tree problem[J]. Information Processing Letters, 1995, 53:109-111.
[12] Bondy J A. Trigraphs[J]. Discrete Mathematics, 1989, 75(1-3):69-79.
Options
Outlines

/

〈 〉