English

运筹学学报 >

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

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

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

展开
  • 1. 河南工业大学理学院, 郑州 450001;
    2. 同济大学电子与信息工程学院, 上海 200092

收稿日期: 2018-11-19

  网络出版日期: 2020-11-18

基金资助

国家自然科学基金（Nos.11571323，61373106）

收起

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

摘要

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

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

本文引用格式

林浩, 林澜 . 区间图最小伸展支撑树问题的最优性刻画[J]. 运筹学学报, 2020 , 24(4) : 153 -158 . DOI: 10.15960/j.cnki.issn.1007-6093.2020.04.014

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

参考文献

[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
文章导航

/

〈 〉