Home  Issues  About JGAA  Instructions for Authors 
DOI: 10.7155/jgaa.00208
Computing All Best Swaps for MinimumStretch Tree Spanners
Vol. 14, no. 2, pp. 287306, 2010. Regular paper.
Abstract In a densely connected communication network, represented by a graph G with nonnegative edge weights, it is often advantageous to route all communication on a sparse spanning subnetwork, typically a spanning tree of G. We consider a tree spanner T of G which guarantees that for any two nodes, their distance in T is at most k times their distance in G, where k, called the stretch, is as small as possible. When an edge of the communication tree T fails, network functionality may be restored by reconnecting the two separated parts of the tree with a swap edge. In situations where the failure can be repaired rapidly, such a quick fix is preferred over the recomputation of an entirely new minimumstretch tree, because it is much closer to the previous solution and hence requires far fewer adjustments in the routing scheme. We are therefore interested in the problem of finding for any possibly failing edge in the spanner T, a best swap edge that minimizes the stretch of the new tree. We show how all these best swap edges can be computed in total time O(m^{2} logn) in graphs with arbitrary nonnegative edge weights. For graphs with unit weight edges, we present an O(n^{3}) time algorithm. Furthermore, we present a distributed algorithm for computing the best swap for each edge in the tree spanner.

Submitted: September 2009.
Reviewed: April 2010.
Accepted: April 2010.
Final: April 2010.
Published: June 2010.
Communicated by
Ulrik Brandes

Journal Supporters
