Tree spanner

A tree k-spanner (or simply k-spanner) of a graph $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$.

Theorems

There are several known results about tree spanners. A significant number of these were produced in a paper entitled Tree Spanners written by mathematicians Leizhen Cai and Derek Corneil, which explores theoretical and algorithmic problems associated with tree spanners. Some of the conclusions from that paper are listed below:

Theorem 1: If H is the spanning subgraph of a weighted graph $G=(V,E;w)$, then these statements are equivalent:

(a) $H$ is a t-spanner of $G$ for every pair of vertices of $x$ and $y$ of $G$.

(b) For every edge $xy$ in $V$, $d_H$(x; y) ≤ t * $d_G$(x; y).

(c) For every edge $xy$ in E\E(H), d_H(x; y) <= t * d_G(x; y).

(d) For every edge $xy$ in E, d_H(x; y) <= t * w(xy).

(e) For every edge $xy$ in E\E(H), d_H(x; y) <= t*w(xy).

Theorem 2: Let $D$ and $G$ be directed and undirected weighted graphs respectively, $S$ and $T$ be spanning trees of $D$ and $G$,and $Q$ be a quasitree of $D$. The following problems can be solved in O(m) time.

(a)Determine the stretch index of $T$.

(b)Is $S$ a tree spanner?

(c)Is $Q$ a quasitree spanner?

Theorem 3: Let $H$ be a minimal 1-spanner of a weighted graph $G$, and let $xy$ be an edge of $G$. The following statements are equivalent:

(a) The edge xy belongs to H.

(b) For every vertex z in V\{x,y}, d_G(x; z) + d_G(z; y) > w(xy)

(c) The distance d_G-xy(x; y) > $w$(xy)

Theorem 4: The minimum (or optimal) 1-spanner of a weighted graph can be found in O(mn + n2log n) time.

Theorem 5: The tree 1-spanner of a weighted graph G is a minimum spanning tree. Furthermore, every tree 1-spanner admissible weighted graph contains a unique minimum spanning tree.

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.