TREE SPANNERS

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.