TREE SPANNERS

被引:121
作者
CAI, LZ [1 ]
CORNEIL, DG [1 ]
机构
[1] UNIV TORONTO,DEPT COMP SCI,TORONTO,ON M5S 1A4,CANADA
关键词
GRAPH ALGORITHM; NP-COMPLETE; TREE SPANNER; SPANNING TREE; DISTANCE;
D O I
10.1137/S0895480192237403
中图分类号
O29 [应用数学];
学科分类号
070104 ;
摘要
A tree t-spanner T of a graph G is a spanning tree in which the distance between every pair of vertices is at most t times their distance in G. This notion is motivated by applications in communication networks, distributed systems, and network design. This paper studies graph-theoretic, algorithmic, and complexity issues about tree spanners. It is shown that a tree 1-spanner, if it exists, in a weighted graph with m edges and n vertices is a minimum spanning tree and can be found in O(m log beta(m, n)) time, where beta(m, n) = min{iota\log((iota)) n less than or equal to m/n}. On the other hand, for any fixed t > 1, the problem of determining the existence of a tree t-spanner in a weighted graph is proven to be NP-complete. For unweighted graphs, it is shown that constructing a tree t-spanner takes linear time, whereas determining the existence of a tree t-spanner is NP-complete for any fixed t greater than or equal to 4. A theorem that captures the structure of tree 2-spanners is presented for unweighted graphs. For digraphs, an O((m + n)alpha(m, n)) algorithm is provided for finding a tree t-spanner with t as small as possible, where alpha(m, n) is a functional inverse of Ackerman's function. The results for tree spanners on undirected graphs are extended to ''quasi-tree spanners'' on digraphs. Furthermore, linear-time algorithms are derived for verifying tree spanners and quasi-tree spanners.
引用
收藏
页码:359 / 387
页数:29
相关论文
共 32 条
  • [1] Aho Alfred V., 1974, DESIGN ANAL COMPUTER
  • [2] ON SPARSE SPANNERS OF WEIGHTED GRAPHS
    ALTHOFER, I
    DAS, G
    DOBKIN, D
    JOSEPH, D
    SOARES, J
    [J]. DISCRETE & COMPUTATIONAL GEOMETRY, 1993, 9 (01) : 81 - 100
  • [3] ON OPTIMAL REALIZATIONS OF FINITE METRIC-SPACES BY GRAPHS
    ALTHOFER, I
    [J]. DISCRETE & COMPUTATIONAL GEOMETRY, 1988, 3 (02) : 103 - 122
  • [4] EASY PROBLEMS FOR TREE-DECOMPOSABLE GRAPHS
    ARNBORG, S
    LAGERGREN, J
    SEESE, D
    [J]. JOURNAL OF ALGORITHMS, 1991, 12 (02) : 308 - 340
  • [5] Awerbuch B., 1992, EFFICIENT BROADCAST
  • [6] Bhatt S., 1986, 27th Annual Symposium on Foundations of Computer Science (Cat. No.86CH2354-9), P274, DOI 10.1109/SFCS.1986.38
  • [7] CYCLES IN WEIGHTED GRAPHS
    BONDY, JA
    FAN, GH
    [J]. COMBINATORICA, 1991, 11 (03) : 191 - 205
  • [8] TRIGRAPHS
    BONDY, JA
    [J]. DISCRETE MATHEMATICS, 1989, 75 (1-3) : 69 - 79
  • [9] BONDY JA, 1976, GRAPH THEORY APPLICA
  • [10] CAI L, 1992, THESIS U TORONTO TOR