A tree ''k''-spanner (or simply ''k''-spanner) of a

graph Graph may refer to: Mathematics *Graph (discrete mathematics), a structure made of vertices and edges **Graph theory, the study of such graphs and their properties *Graph (topology), a topological space resembling a graph in the sense of discre ...

G

is a spanning subtree

T

G

in which the distance between every pair of vertices is at most

k

times their

distance Distance is a numerical or occasionally qualitative measurement of how far apart objects or points are. In physics or everyday usage, distance may refer to a physical length or an estimation based on other criteria (e.g. "two counties over"). ...

G

Known 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 Derek Gordon Corneil is a Canadian mathematician and computer scientist, a professor ''emeritus'' of computer science at the University of Toronto, and an expert in graph algorithms and graph theory. Life When he was leaving high school, 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. # A tree 1-spanner, if it exists, is a minimum spanning tree and can be found in

\mathcal(m \log \beta (m,n))

time (in terms of complexity) for a weighted graph, where

\beta(m,n) = \min\left\

. Furthermore, every tree 1-spanner admissible weighted graph contains a unique minimum spanning tree. # A tree 2-spanner can be constructed in

\mathcal(m+n)

time, and the tree

t

-spanner problem is

NP-complete In computational complexity theory, a problem is NP-complete when: # it is a problem for which the correctness of each solution can be verified quickly (namely, in polynomial time) and a brute-force search algorithm can find a solution by tryin ...

for any fixed integer

t > 3

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

\mathcal((m+n)\cdot\alpha(m+n,n))

, where

\alpha(m+n,n)

is a functional inverse of the

Ackermann function In computability theory, the Ackermann function, named after Wilhelm Ackermann, is one of the simplest and earliest-discovered examples of a total computable function that is not primitive recursive. All primitive recursive functions are total ...

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

\mathcal(mn+n^2\log(n))

time. # 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. # 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

\mathcal(m \log \beta(m,n))

time.

References

*{{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 . Spanning tree

Known Results

See also

References