A Novel Algorithm for the All-Best-Swap-Edge Problem on Tree Spanners

File

Author Details

Davide Bilò

Department of Humanities and Social Sciences, University of Sassari, Italy

Kleitos Papadopoulos

InSPIRE, Agamemnonos 20, Nicosia, 1041, Cyprus

Cite AsGet BibTex

Davide Bilò and Kleitos Papadopoulos. A Novel Algorithm for the All-Best-Swap-Edge Problem on Tree Spanners. In 29th International Symposium on Algorithms and Computation (ISAAC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 123, pp. 7:1-7:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.ISAAC.2018.7

Abstract

Given a 2-edge connected, unweighted, and undirected graph G with n vertices and m edges, a sigma-tree spanner is a spanning tree T of G in which the ratio between the distance in T of any pair of vertices and the corresponding distance in G is upper bounded by sigma. The minimum value of sigma for which T is a sigma-tree spanner of G is also called the stretch factor of T. We address the fault-tolerant scenario in which each edge e of a given tree spanner may temporarily fail and has to be replaced by a best swap edge, i.e. an edge that reconnects T-e at a minimum stretch factor. More precisely, we design an O(n^2) time and space algorithm that computes a best swap edge of every tree edge. Previously, an O(n^2 log^4 n) time and O(n^2+m log^2n) space algorithm was known for edge-weighted graphs [Bilò et al., ISAAC 2017]. Even if our improvements on both the time and space complexities are of a polylogarithmic factor, we stress the fact that the design of a o(n^2) time and space algorithm would be considered a breakthrough.

Subject Classification

ACM Subject Classification

Theory of computation → Graph algorithms analysis

Keywords

Transient edge failure
best swap edges
tree spanner

Metrics

Access Statistics
Total Accesses (updated on a weekly basis)

0

PDF Downloads

0

Metadata Views

References

Michael A. Bender and Martin Farach-Colton. The Level Ancestor Problem simplified. Theor. Comput. Sci., 321(1):5-12, 2004. URL: http://dx.doi.org/10.1016/j.tcs.2003.05.002.
Davide Bilò, Feliciano Colella, Luciano Gualà, Stefano Leucci, and Guido Proietti. A Faster Computation of All the Best Swap Edges of a Tree Spanner. In Christian Scheideler, editor, Structural Information and Communication Complexity - 22nd International Colloquium, SIROCCO 2015, Montserrat, Spain, July 14-16, 2015, Post-Proceedings, volume 9439 of Lecture Notes in Computer Science, pages 239-253. Springer, 2015. URL: http://dx.doi.org/10.1007/978-3-319-25258-2_17.
Davide Bilò, Feliciano Colella, Luciano Gualà, Stefano Leucci, and Guido Proietti. An Improved Algorithm for Computing All the Best Swap Edges of a Tree Spanner. In Yoshio Okamoto and Takeshi Tokuyama, editors, 28th International Symposium on Algorithms and Computation, ISAAC 2017, December 9-12, 2017, Phuket, Thailand, volume 92 of LIPIcs, pages 14:1-14:13. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2017. URL: http://dx.doi.org/10.4230/LIPIcs.ISAAC.2017.14.
Davide Bilò, Feliciano Colella, Luciano Gualà, Stefano Leucci, and Guido Proietti. Effective Edge-Fault-Tolerant Single-Source Spanners via Best (or Good) Swap Edges. In Shantanu Das and Sébastien Tixeuil, editors, Structural Information and Communication Complexity - 24th International Colloquium, SIROCCO 2017, Porquerolles, France, June 19-22, 2017, Revised Selected Papers, volume 10641 of Lecture Notes in Computer Science, pages 303-317. Springer, 2017. URL: http://dx.doi.org/10.1007/978-3-319-72050-0_18.
Davide Bilò, Luciano Gualà, and Guido Proietti. Finding Best Swap Edges Minimizing the Routing Cost of a Spanning Tree. Algorithmica, 68(2):337-357, 2014. URL: http://dx.doi.org/10.1007/s00453-012-9674-y.
Davide Bilò, Luciano Gualà, and Guido Proietti. A Faster Computation of All the Best Swap Edges of a Shortest Paths Tree. Algorithmica, 73(3):547-570, 2015. URL: http://dx.doi.org/10.1007/s00453-014-9912-6.
Shantanu Das, Beat Gfeller, and Peter Widmayer. Computing All Best Swaps for Minimum-Stretch Tree Spanners. J. Graph Algorithms Appl., 14(2):287-306, 2010. URL: http://jgaa.info/accepted/2010/DasGfellerWidmayer2010.14.2.pdf.
Paola Flocchini, Antonio Mesa Enriques, Linda Pagli, Giuseppe Prencipe, and Nicola Santoro. Efficient Protocols for Computing the Optimal Swap Edges of a Shortest Path Tree. In Exploring New Frontiers of Theoretical Informatics, IFIP 18th World Computer Congress, TC1 3rd International Conference on Theoretical Computer Science (TCS2004), 22-27 August 2004, Toulouse, France, pages 153-166, 2004. URL: http://dx.doi.org/10.1007/1-4020-8141-3_14.
Paola Flocchini, Antonio Mesa Enriques, Linda Pagli, Giuseppe Prencipe, and Nicola Santoro. Point-of-Failure Shortest-Path Rerouting: Computing the Optimal Swap Edges Distributively. IEICE Transactions, 89-D(2):700-708, 2006. URL: http://dx.doi.org/10.1093/ietisy/e89-d.2.700.
Paola Flocchini, Linda Pagli, Giuseppe Prencipe, Nicola Santoro, and Peter Widmayer. Computing all the best swap edges distributively. J. Parallel Distrib. Comput., 68(7):976-983, 2008. URL: http://dx.doi.org/10.1016/j.jpdc.2008.03.002.
Dov Harel and Robert Endre Tarjan. Fast Algorithms for Finding Nearest Common Ancestors. SIAM J. Comput., 13(2):338-355, 1984. URL: http://dx.doi.org/10.1137/0213024.
Giuseppe F. Italiano and Rajiv Ramaswami. Maintaining Spanning Trees of Small Diameter. Algorithmica, 22(3):275-304, 1998. URL: http://dx.doi.org/10.1007/PL00009225.
Hiro Ito, Kazuo Iwama, Yasuo Okabe, and Takuya Yoshihiro. Polynomial-Time Computable Backup Tables for Shortest-Path Routing. In Proc. of the 10th Intl. Colloquium Structural Information and Communication Complexity, pages 163-177, 2003.
Enrico Nardelli, Guido Proietti, and Peter Widmayer. A faster computation of the most vital edge of a shortest path. Inf. Process. Lett., 79(2):81-85, 2001. URL: http://dx.doi.org/10.1016/S0020-0190(00)00175-7.
Seth Pettie. Sensitivity Analysis of Minimum Spanning Trees in Sub-inverse-Ackermann Time. In Proc. of the 16th Intl. Symposium on Algorithms and Computation, pages 964-973, 2005. URL: http://dx.doi.org/10.1007/11602613_96.
Guido Proietti. Dynamic Maintenance Versus Swapping: An Experimental Study on Shortest Paths Trees. In Proc. of the 4th Intl. Workshop on Algorithm Engineering, pages 207-217, 2000. URL: http://dx.doi.org/10.1007/3-540-44691-5_18.
Aleksej Di Salvo and Guido Proietti. Swapping a failing edge of a shortest paths tree by minimizing the average stretch factor. Theor. Comput. Sci., 383(1):23-33, 2007. URL: http://dx.doi.org/10.1016/j.tcs.2007.03.046.
Bang Ye Wu, Chih-Yuan Hsiao, and Kun-Mao Chao. The Swap Edges of a Multiple-Sources Routing Tree. Algorithmica, 50(3):299-311, 2008. URL: http://dx.doi.org/10.1007/s00453-007-9080-z.