Reference articles on history, science, culture and more
Surprise meSurprise meSubscribe
Encyclopedia

Tree spanner

Wikipedia contributorsAdapted for Fathomly · View authors
1 min read
Source updated March 10, 2026
Image credit is listed at the end of this article.

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.

01Known Results

There are several papers written on the subject of tree spanners. One of these was entitled Tree Spanners 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 {\mathcal {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.
  2. A tree 2-spanner can be constructed in {\mathcal {O}}(m+n) time, and the tree t-spanner problem is NP-complete for any fixed integer t>3.
  3. The complexity for finding a minimum tree spanner in a digraph is {\mathcal {O}}((m+n)\cdot \alpha (m+n,n)), where \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 {\mathcal {O}}(mn+n^{2}\log(n)) time.
  5. 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.
  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 {\mathcal {O}}(m\log \beta (m,n)) time.
Watch videos about Tree spannerExplainers and documentaries on YouTube (opens in a new tab)

Sources and credits

This article is adapted from the Wikipedia article “Tree spanner”, written by its contributors and licensed under CC BY-SA 4.0. Fathomly has changed the layout, removed citation markers, navigation and maintenance notices, and adjusted punctuation. This adapted version is shared under the same license. For references, see the original article.

Images, from Wikimedia Commons:

Fathomly is not affiliated with or endorsed by the Wikimedia Foundation. Spotted a problem? Tell us.

Continue exploring

Related topics

Glossary of graph theory

This is a glossary of graph theory. Graph theory is the study of graphs, systems of nodes or vertices connected in pairs by lines or edges.

Geometric spanner

A geometric spanner or a t-spanner graph or a t-spanner was initially introduced as a weighted graph over a set of points as its vertices for which there is a t-path between any pair of vertices for a fixed parameter t. A t-path is defined as a path through the graph with weight at most t times the spatial distance between its endpoints.