DIMACS TR: 96-13
Independent Spanning Trees with Small Stretch Factors
Authors: Fred Annexstein, Ken Berman and Ram Swaminathan
A pair of spanning trees rooted at a vertex "r" are independent if for every
vertex "v" the pair of unique tree paths from "v" to the root "r" are disjoint.
This paper presents the first analysis of the path lengths involved in
independent spanning trees in 2-edge-connected and 2-vertex-connected
graphs. We present upper and lower bounds on the stretch factors of pairs of
independent spanning trees, where the stretch factor of a spanning tree is
defined to be the maximum ratio between the length of paths in the tree to
the root to the length of the shortest path in the graph to the root. We
prove that if "G" is a 2-edge-connected graph with the property that every
edge lies on a cycle of size at most "h", then we can construct in linear time
a pair of edge-independent spanning trees whose stretch factors are bounded
by O(h). In fact, we prove a more general result, namely that the stretch
factor of both independent trees can be bounded by a minimax length of ears
with respect to a certain class of ear decompositions of the graph. We
demonstrate analogous constructions of vertex-independent spanning trees with
bounded stretch factors for the class of 2-vertex-connected graphs. We show
that our upper bounds are existentially optimal, that is, there are classes
of graphs for which our bounds are tight.
The last author would like to acknowledge the hospitality of DIMACS Center.
Paper Available at:
DIMACS Home Page