Document Open Access Logo

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

Authors Davide Bilò , Kleitos Papadopoulos

PDF
Thumbnail PDF

File

LIPIcs.ISAAC.2018.7.pdf
  • Filesize: 0.51 MB
  • 12 pages

Document Identifiers

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

  1. 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.
  2. 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.
  3. 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.
  4. 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.
  5. 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.
  6. 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.
  7. 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.
  8. 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.
  9. 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.
  10. 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.
  11. 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.
  12. 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.
  13. 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. Google Scholar
  14. 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.
  15. 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.
  16. 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.
  17. 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.
  18. 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.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact