Tree spanner

A tree k-spanner (or simply k-spanner) of a graph ${\displaystyle G}$ is a spanning subtree ${\displaystyle T}$ of ${\displaystyle G}$ in which the distance between every pair of vertices is at most ${\displaystyle k}$ times their distance in ${\displaystyle 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. ${\displaystyle n}$ is always the number of vertices of the graph, and ${\displaystyle m}$ is its number of edges.

1. A tree 1-spanner, if it exists, is a minimum spanning tree and can be found in ${\displaystyle {\mathcal {O}}(m\log \beta (m,n))}$ time (in terms of complexity) for a weighted graph, where ${\displaystyle \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.
2. A tree 2-spanner can be constructed in ${\displaystyle {\mathcal {O}}(m+n)}$ time, and the tree ${\displaystyle t}$-spanner problem is NP-complete for any fixed integer ${\displaystyle t>3}$.
3. The complexity for finding a minimum tree spanner in a digraph is ${\displaystyle {\mathcal {O}}((m+n)\cdot \alpha (m+n,n))}$, where ${\displaystyle \alpha (m+n,n)}$ is a functional inverse of the Ackermann function
4. The minimum 1-spanner of a weighted graph can be found in ${\displaystyle {\mathcal {O}}(mn+n^{2}\log(n))}$ time.
5. For any fixed rational number ${\displaystyle 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.
6. A tree spanner (or a minimum tree spanner) of a digraph can be found in linear time.
7. A digraph contains at most one tree spanner.
8. The quasi-tree spanner of a weighted digraph can be found in ${\displaystyle {\mathcal {O}}(m\log \beta (m,n))}$ time.

See also

• Graph spanner
• Geometric spanner

References

• Handke, Dagmar; Kortsarz, Guy (2000), "Tree spanners for subgraphs and related tree covering problems", Graph-Theoretic Concepts in Computer Science: 26th International Workshop, WG 2000 Konstanz, Germany, June 15–17, 2000, Proceedings, Lecture Notes in Computer Science, vol. 1928, pp. 206–217, doi:10.1007/3-540-40064-8_20, ISBN 978-3-540-41183-3.

This page was last edited on 20 February 2020, at 21:30