Tree spanner

Uses your system voice; voice and rate in settings.

Snapshot

≈ 2 min read

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the 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 .

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 .

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, 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{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. 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 . 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 The minimum 1-spanner of a weighted graph can be found in \mathcal{O}(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{O}(m \log \beta(m,n)) time.

References

.

Text derived from https://en.wikipedia.org/w/index.php?oldid=1342719063 under CC BY-SA 4.0; modifications have been made.

Provenance

snapshot enwiki-001342719063 · captured 1773135423.0 · version history

Cite this page as: encyclopegia.org, “Tree spanner”, snapshot enwiki-001342719063. https://encyclopegia.org/a/tree-spanner

Sources cited in this revision

No external citation was extracted for this revision. That is a statement about the source, not a claim that none exists.