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.

Known Results

There are several papers written on the subject of tree spanners. One of these was entitled Tree Spanners[1] 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:

(1) A tree 1-spanner, if it exists, is a minimum spanning tree and can be found in O(m log β (m,n))time (in terms of complexity) for a weighted graph, where β (m,n) = min{i| log^{t} n \leq m/n}.

(2) A tree 2-spanner can be constructed in linear 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 O((m+n)α(m+n,n)) , where α(m+n,n) is a functional inverse of the Ackermann function, m is the number of vertices of the graph, and n is its number of edges.

(4) The minimum 1-spanner of a weighted graph can be found in O(m \times n+n^2 \times 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 O(m \times log β(m,n)) time.

(9) 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.

(10) A tree 2-spanner (if it exists) of a graph can be found in O(m + n) time.

References

  1. ↑ http://epubs.siam.org/doi/abs/10.1137/S0895480192237403


This article is issued from Wikipedia - version of the Sunday, January 31, 2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.