Tree Spanners
Leizhen Cai, Derek Gordon Corneil · SIAM Journal on Discrete Mathematics · 1995
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 \{ i|\log^{( i )} n \leq 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 2-spanner takes linear time, whereas determining the existence of a tree t-spanner is NP-complete for any fixed $t \geq 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.