Document Open Access Logo

Multiple-Edge-Fault-Tolerant Approximate Shortest-Path Trees

Authors Davide Bilò, Luciano Gualà, Stefano Leucci, Guido Proietti

PDF
Thumbnail PDF

File

LIPIcs.STACS.2016.18.pdf
  • Filesize: 0.82 MB
  • 14 pages

Document Identifiers

Author Details

Davide Bilò
Luciano Gualà
Stefano Leucci
Guido Proietti

Cite As Get BibTex

Davide Bilò, Luciano Gualà, Stefano Leucci, and Guido Proietti. Multiple-Edge-Fault-Tolerant Approximate Shortest-Path Trees. In 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 47, pp. 18:1-18:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.STACS.2016.18

Abstract

Let G be an n-node and m-edge positively real-weighted undirected graph. For any given integer f >= 1, we study the problem of designing a sparse f-edge-fault-tolerant (f-EFT) sigma-approximate single-source shortest-path tree (sigma-ASPT), namely a subgraph of G having as few edges as possible and which, following the failure of a set F of at most f edges in G, contains paths from a fixed source that are stretched at most by a factor of sigma. To this respect, we provide an algorithm that efficiently computes an f-EFT (2|F|+1)-ASPT of size O(f n). Our structure improves on a previous related construction designed for unweighted graphs, having the same size but guaranteeing a larger stretch factor of 3(f+1), plus an additive term of (f+1)*log(n).

Then, we show how to convert our structure into an efficient f-EFT single-source distance oracle (SSDO), that can be built in ~{O}(f m) time, has size O(fn *log^2(n)), and is able to report, after the failure of the edge set F, in O(|F|^2 * log^2(n)) time a (2|F|+1)-approximate distance from the source to any node, and a corresponding approximate path in the same amount of time plus the path's size. Such an oracle is obtained by handling another fundamental problem, namely that of updating a minimum spanning forest (MSF) of G after that a batch of k simultaneous edge modifications (i.e., edge insertions, deletions and weight changes) is performed. For this problem, we build in O(m * log^3(n)) time a sensitivity oracle of size O(m * log^2(n)), that reports in O(k^2 * log^2(n)) time the (at most 2k) edges either exiting from or entering into the MSF. As a result of independent interest, it is worth noticing that our MSF oracle can be employed to handle arbitrary sequences of o(sqrt[4]{n}/log(n)) (non-simultaneous) updates with a worst-case time per update of o(sqrt{n}). Thus, for relatively short sequences of updates, our oracle should be preferred w.r.t. the best-known (in a worst-case sense) MSF fully-dynamic algorithm, requiring O(sqrt{n}) time per update.

Subject Classification

Keywords
  • fault-tolerant shortest-path tree
  • distance oracle
  • minimum spanning tree

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Stephen Alstrup, Jacob Holm, Kristian de Lichtenberg, and Mikkel Thorup. Maintaining information in fully dynamic trees with top trees. ACM Transactions on Algorithms, 1(2):243-264, 2005. URL: http://doi.acm.org/10.1145/1103963.1103966, URL: http://dx.doi.org/10.1145/1103963.1103966.
  2. Ingo Althöfer, Gautam Das, David P. Dobkin, Deborah Joseph, and José Soares. On sparse spanners of weighted graphs. Discrete & Computational Geometry, 9:81-100, 1993. URL: http://dx.doi.org/10.1007/BF02189308,
  3. Giorgio Ausiello, Paolo Giulio Franciosa, Giuseppe Francesco Italiano, and Andrea Ribichini. On resilient graph spanners. In ESA, pages 85-96, 2013. Google Scholar
  4. Surender Baswana and Neelesh Khanna. Approximate shortest paths avoiding a failed vertex: Near optimal data structures for undirected unweighted graphs. Algorithmica, 66(1):18-50, 2013. URL: http://dx.doi.org/10.1007/s00453-012-9621-y,
  5. Surender Baswana, Kavitha Telikepalli, Kurt Mehlhorn, and Seth Pettie. Additive spanners and (alpha, beta)-spanners. ACM Transactions on Algorithms, 7(1):5, 2010. URL: http://dx.doi.org/10.1145/1868237.1868242,
  6. Aaron Bernstein and David R. Karger. A nearly optimal oracle for avoiding failed vertices and edges. In STOC, pages 101-110, 2009. Google Scholar
  7. Davide Bilò, Fabrizio Grandoni, Luciano Gualà, Stefano Leucci, and Guido Proietti. Improved purely additive fault-tolerant spanners. In ESA, pages 167-178, 2015. Google Scholar
  8. Davide Bilò, Luciano Gualà, Stefano Leucci, and Guido Proietti. Fault-tolerant approximate shortest-path trees. In ESA, pages 137-148, 2014. URL: http://dx.doi.org/10.1007/978-3-662-44777-2_12,
  9. Gilad Braunschvig, Shiri Chechik, and David Peleg. Fault tolerant additive spanners. In WG, pages 206-214, 2012. URL: http://dx.doi.org/10.1007/978-3-642-34611-8_22,
  10. Bernard Chazelle. A minimum spanning tree algorithm with inverse-ackermann type complexity. J. ACM, 47(6):1028-1047, 2000. URL: http://doi.acm.org/10.1145/355541.355562, URL: http://dx.doi.org/10.1145/355541.355562.
  11. Shiri Chechik. New additive spanners. In SODA, pages 498-512, 2013. URL: http://dx.doi.org/10.1137/1.9781611973105.36,
  12. Shiri Chechik. Approximate distance oracles with constant query time. In STOC, pages 654-663, 2014. URL: http://doi.acm.org/10.1145/2591796.2591801, URL: http://dx.doi.org/10.1145/2591796.2591801.
  13. Shiri Chechik, Michael Langberg, David Peleg, and Liam Roditty. Fault-tolerant spanners for general graphs. In STOC, pages 435-444, 2009. Google Scholar
  14. Shiri Chechik, Michael Langberg, David Peleg, and Liam Roditty. f-sensitivity distance oracles and routing schemes. In ESA, pages 84-96, 2010. Google Scholar
  15. Annalisa D'Andrea, Mattia D'Emidio, Daniele Frigioni, Stefano Leucci, and Guido Proietti. Path-fault-tolerant approximate shortest-path trees. In SIROCCO, pages 224-238, 2015. URL: http://dx.doi.org/10.1007/978-3-319-25258-2_16,
  16. Michael Dinitz and Robert Krauthgamer. Fault-tolerant spanners: better and simpler. In PODC, pages 169-178, 2011. Google Scholar
  17. Ran Duan and Seth Pettie. Dual-failure distance and connectivity oracles. In SODA, pages 506-515, 2009. URL: http://dl.acm.org/citation.cfm?id=1496770.1496826.
  18. Michael Elkin and Seth Pettie. A linear-size logarithmic stretch path-reporting distance oracle for general graphs. In SODA, pages 805-821, 2015. URL: http://dx.doi.org/10.1137/1.9781611973730.55,
  19. David Eppstein. Offline algorithms for dynamic minimum spanning tree problems. J. Algorithms, 17(2):237-250, 1994. URL: http://dx.doi.org/10.1006/jagm.1994.1033,
  20. David Eppstein, Zvi Galil, Giuseppe F. Italiano, and Amnon Nissenzweig. Sparsification-a technique for speeding up dynamic graph algorithms (extended abstract). In FOCS, pages 60-69, 1992. URL: http://dx.doi.org/10.1109/SFCS.1992.267818,
  21. Paul Erdős. Extremal problems in graph theory. In Theory of Graphs and its Applications, pages 29-36, 1964. Google Scholar
  22. Greg N. Frederickson. Data structures for on-line updating of minimum spanning trees, with applications. SIAM J. Comput., 14(4):781-798, 1985. URL: http://dx.doi.org/10.1137/0214055,
  23. Fabrizio Grandoni and Virginia Vassilevska Williams. Improved distance sensitivity oracles via fast single-source replacement paths. In FOCS, pages 748-757, 2012. Google Scholar
  24. 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,
  25. Monika Rauch Henzinger and Valerie King. Maintaining minimum spanning forests in dynamic graphs. SIAM J. Comput., 31(2):364-374, 2001. URL: http://dx.doi.org/10.1137/S0097539797327209,
  26. Jacob Holm, Kristian de Lichtenberg, and Mikkel Thorup. Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity. J. ACM, 48(4):723-760, 2001. URL: http://doi.acm.org/10.1145/502090.502095, URL: http://dx.doi.org/10.1145/502090.502095.
  27. Enrico Nardelli, Guido Proietti, and Peter Widmayer. Swapping a failing edge of a single source shortest paths tree is good and fast. Algorithmica, 35(1):56-74, 2003. Google Scholar
  28. Merav Parter. Vertex fault tolerant additive spanners. In DISC, pages 167-181, 2014. URL: http://dx.doi.org/10.1007/978-3-662-45174-8_12,
  29. Merav Parter. Dual failure resilient BFS structure. In PODC, pages 481-490, 2015. Google Scholar
  30. Merav Parter and David Peleg. Sparse fault-tolerant BFS trees. In ESA, pages 779-790, 2013. URL: http://dx.doi.org/10.1007/978-3-642-40450-4_66,
  31. Merav Parter and David Peleg. Fault tolerant approximate BFS structures. In SODA, pages 1073-1092, 2014. Google Scholar
  32. Mikkel Thorup and Uri Zwick. Approximate distance oracles. J. ACM, 52(1):1-24, 2005. URL: http://doi.acm.org/10.1145/1044731.1044732, URL: http://dx.doi.org/10.1145/1044731.1044732.
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 About DROPS Imprint Privacy Contact