Tree spanner explained

G is a spanning subtree T of G in which the distance between every pair of vertices is at most k times their distance in G .

Known Results

There are several papers written on the subject of tree spanners. One of these was entitled Tree Spanners^[1] written by mathematicians Leizhen Cai and Derek Corneil, which explored theoretical and algorithmic problems associated with tree spanners. Some of the conclusions from that paper are listed below.

n is always the number of vertices of the graph, and m is its number of edges.

1. A tree 1-spanner, if it exists, is a minimum spanning tree and can be found in

l{O}(m log \beta (m,n)) time (in terms of complexity) for a weighted graph, where \beta(m,n) = min \left\{i\mid log ^{i} n \leq m/n\right\} . Furthermore, every tree 1-spanner admissible weighted graph contains a unique minimum spanning tree.

1. A tree 2-spanner can be constructed in

l{O}(m+n) time, and the tree t -spanner problem is NP-complete for any fixed integer t > 3 .

1. The complexity for finding a minimum tree spanner in a digraph is

l{O}((m+n) ⋅ \alpha(m+n,n)) , where \alpha(m + n,n) is a functional inverse of the Ackermann function

1. The minimum 1-spanner of a weighted graph can be found in

l{O}(mn+n ^{2log(n))} time.

1. For any fixed rational number

t > 1 , it is NP-complete to determine whether a weighted graph contains a tree t-spanner, even if all edge weights are positive integers.

1. A tree spanner (or a minimum tree spanner) of a digraph can be found in linear time.
2. A digraph contains at most one tree spanner.
3. The quasi-tree spanner of a weighted digraph can be found in

l{O}(m log \beta(m,n)) time.

See also

• Graph spanner
• Geometric spanner

References

• .

Notes and References

1. 10.1137/S0895480192237403. Tree Spanners. SIAM Journal on Discrete Mathematics. 8. 3. 359–387. 1995. Cai. Leizhen. Corneil. Derek G..