Abstract
In network communication systems, frequently messages are routed along a minimum diameter spanning tree (MDST) of the network, to minimize the maximum travel time of messages. When a transient failure disables an edge of the MDST, the network is disconnected, and a temporary replacement edge must be chosen, which should ideally minimize the diameter of the new spanning tree. Preparing for the failure of any edge of the MDST, the all-best-swaps (ABS) problem asks for finding the best swap for every edge of the MDST. Given a 2-edge-connected weighted graph G = (V,E), where |V| = n and |E| = m, we solve the ABS problem in \( O\left( m\log n \right) \) time and O(m ) space, thus considerably improving upon the decade-old previously best solution, which requires \(O(n\sqrt{m})\) time and O(m) space, for \(m=o\left(n^2/ \log^2 n\right)\).
We gratefully acknowledge the support of the Swiss SBF under contract no. C05.0047 within COST-295 (DYNAMO) of the European Union.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Di Salvo, A., Proietti, G.: Swapping a Failing Edge of a Shortest Paths Tree by Minimizing the Average Stretch Factor. Theor. Comp. Sci. 383(1), 23–33 (2007)
Flocchini, P., Enriques, A.M., Pagli, L., Prencipe, G., Santoro, N.: Point-of-failure Shortest-path Rerouting: Computing the Optimal Swap Edges Distributively. IEICE Transactions on Information and Systems E89-D(2), 700–708 (2006)
Flocchini, P., Pagli, L., Prencipe, G., Santoro, N., Widmayer, P.: Computing All the Best Swap Edges Distributively. Journal of Parallel and Distributed Computing (in press, 2008)
Fredman, M.L., Tarjan, R.E.: Fibonacci Heaps and Their Uses in Improved Network Optimization Algorithms. J. ACM 34(3), 596–615 (1987)
Gfeller, B.: Faster swap edge computation in minimum diameter spanning trees. Technical Report 597, ETH Zurich (June 2008), http://www.inf.ethz.ch/research/disstechreps/techreports
Gfeller, B., Santoro, N., Widmayer, P.: A Distributed Algorithm for Finding All Best Swap Edges of a Minimum Diameter Spanning Tree. In: Pelc, A. (ed.) DISC 2007. LNCS, vol. 4731, pp. 268–282. Springer, Heidelberg (2007)
Harel, D., Tarjan, R.E.: Fast Algorithms for Finding Nearest Common Ancestors. SIAM Journal on Computing 13(2), 338–355 (1984)
Ito, H., Iwama, K., Okabe, Y., Yoshihiro, T.: Single Backup Table Schemes for Shortest-path Routing. Theor. Comp. Sci. 333(3), 347–353 (2005)
Nardelli, E., Proietti, G., Widmayer, P.: Finding All the Best Swaps of a Minimum Diameter Spanning Tree Under Transient Edge Failures. Journal of Graph Algorithms and Applications 5(5), 39–57 (2001)
Nardelli, E., Proietti, G., Widmayer, P.: Swapping a Failing Edge of a Single Source Shortest Paths Tree Is Good and Fast. Algorithmica 35(1), 56–74 (2003)
Proietti, G.: Dynamic Maintenance Versus Swapping: An Experimental Study on Shortest Paths Trees. In: Näher, S., Wagner, D. (eds.) WAE 2000. LNCS, vol. 1982, pp. 207–217. Springer, Heidelberg (2001)
Wu, B.Y., Hsiao, C.-Y., Chao, K.-M.: The Swap Edges of a Multiple-Sources Routing Tree. Algorithmica 50(3), 299–311 (2008)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2008 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Gfeller, B. (2008). Faster Swap Edge Computation in Minimum Diameter Spanning Trees. In: Halperin, D., Mehlhorn, K. (eds) Algorithms - ESA 2008. ESA 2008. Lecture Notes in Computer Science, vol 5193. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-87744-8_38
Download citation
DOI: https://doi.org/10.1007/978-3-540-87744-8_38
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-87743-1
Online ISBN: 978-3-540-87744-8
eBook Packages: Computer ScienceComputer Science (R0)