thumb|The lowest <math>k</math> tree spanner for the graph <math>G</math> is <math>k=3/2</math> because of the necessarily longer path between the red vertices, which is <math>3/2</math> times as long as the shortest distance between them in <math>G</math>
A '''tree ''k''-spanner''' (or simply '''''k''-spanner''') of a graph <math>G</math> is a spanning subtree <math>T</math> of <math>G</math> in which the distance between every pair of vertices is at most <math>k</math> times their distance in <math>G</math>.
==Known Results==
There are several papers written on the subject of tree spanners. One of these was entitled ''Tree Spanners''<ref>{{Cite journal | doi=10.1137/S0895480192237403|title = Tree Spanners| journal=SIAM Journal on Discrete Mathematics| volume=8| issue=3| pages=359–387|year = 1995|last1 = Cai|first1 = Leizhen| last2=Corneil| first2=Derek G.}}</ref> 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. <math>n</math> is always the number of vertices of the graph, and <math>m</math> is its number of edges.
# A tree 1-spanner, if it exists, is a minimum spanning tree and can be found in <math>\mathcal{O}(m \log \beta (m,n))</math> time (in terms of complexity) for a weighted graph, where <math>\beta(m,n) = \min\left\{i\mid \log^{i} n \leq m/n\right\}</math>. Furthermore, every tree 1-spanner admissible weighted graph contains a unique minimum spanning tree. # A tree 2-spanner can be constructed in <math>\mathcal{O}(m+n)</math> time, and the tree <math>t</math>-spanner problem is NP-complete for any fixed integer <math>t > 3</math>. # The complexity for finding a minimum tree spanner in a digraph is <math>\mathcal{O}((m+n)\cdot\alpha(m+n,n))</math>, where <math>\alpha(m+n,n)</math> is a functional inverse of the Ackermann function # The minimum 1-spanner of a weighted graph can be found in <math>\mathcal{O}(mn+n^2\log(n))</math> time. # For any fixed rational number <math>t > 1</math>, it is NP-complete to determine whether a weighted graph contains a tree t-spanner, even if all edge weights are positive integers. # A tree spanner (or a minimum tree spanner) of a digraph can be found in linear time. # A digraph contains at most one tree spanner. # The quasi-tree spanner of a weighted digraph can be found in <math>\mathcal{O}(m \log \beta(m,n))</math> time.
== See also == *Graph spanner *Geometric spanner
==References== {{Reflist}} *{{citation | last1 = Handke | first1 = Dagmar | last2 = Kortsarz | first2 = Guy | contribution = Tree spanners for subgraphs and related tree covering problems | doi = 10.1007/3-540-40064-8_20 | pages = 206–217 | series = Lecture Notes in Computer Science | title = Graph-Theoretic Concepts in Computer Science: 26th International Workshop, WG 2000 Konstanz, Germany, June 15–17, 2000, Proceedings | volume = 1928 | year = 2000| isbn = 978-3-540-41183-3 }}.
Category:Spanning tree Category:NP-complete problems