DIMACS TR: 96-13

Independent Spanning Trees with Small Stretch Factors



Authors: Fred Annexstein, Ken Berman and Ram Swaminathan

ABSTRACT

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: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1996/96-13.ps.gz


DIMACS Home Page