Document Open Access Logo

Compact and Fast Sensitivity Oracles for Single-Source Distances

Authors Davide Bilo, Luciano Guala, Stefano Leucci, Guido Proietti

PDF
Thumbnail PDF

File

LIPIcs.ESA.2016.13.pdf
  • Filesize: 0.6 MB
  • 14 pages

Document Identifiers

Author Details

Davide Bilo
Luciano Guala
Stefano Leucci
Guido Proietti

Cite As Get BibTex

Davide Bilo, Luciano Guala, Stefano Leucci, and Guido Proietti. Compact and Fast Sensitivity Oracles for Single-Source Distances. In 24th Annual European Symposium on Algorithms (ESA 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 57, pp. 13:1-13:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.ESA.2016.13

Abstract

Let s denote a distinguished source vertex of a non-negatively real weighted and undirected graph G with n vertices and m edges. In this paper we present two efficient single-source approximate-distance sensitivity oracles, namely compact data structures which are able to quickly report an approximate (by a multiplicative stretch factor) distance from s to any node of G following the failure of any edge in G. More precisely, we first present a sensitivity oracle of size O(n) which is able to report 2-approximate distances from the source in O(1) time. Then, we further develop our construction by building, for any 0<epsilon<1, another sensitivity oracle having size O(n*1/epsilon*log(1/epsilon)), and is able to report a (1+epsilon)-approximate distance from s to any vertex of G in O(log(n)*1/epsilon*log(1/epsilon)) time. Thus, this latter oracle is essentially optimal as far as size and stretch are concerned, and it only asks for a logarithmic query time. Finally, our results are complemented with a space lower bound for the related class of single-source additively-stretched sensitivity oracles, which is helpful to realize the hardness of designing compact oracles of this type.

Subject Classification

Keywords
  • fault-tolerant shortest-path tree
  • approximate distance
  • distance sensitivity oracle

Metrics

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

References

  1. 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.
  2. 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.
  3. Omer Berkman and Uzi Vishkin. Finding level-ancestors in trees. J. Comput. Syst. Sci., 48(2):214-230, 1994. URL: http://dx.doi.org/10.1016/S0022-0000(05)80002-9.
  4. Aaron Bernstein and David R. Karger. A nearly optimal oracle for avoiding failed vertices and edges. In STOC, pages 101-110, 2009. Google Scholar
  5. 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.
  6. Davide Bilò, Luciano Gualà, Stefano Leucci, and Guido Proietti. Multiple-edge-fault-tolerant approximate shortest-path trees. In STACS, pages 18:1-18:14, 2016. Google Scholar
  7. Shiri Chechik, Michael Langberg, David Peleg, and Liam Roditty. f-sensitivity distance oracles and routing schemes. In ESA, pages 84-96, 2010. Google Scholar
  8. 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.
  9. Erik D. Demaine, Gad M. Landau, and Oren Weimann. On cartesian trees and range minimum queries. Algorithmica, 68(3):610-625, 2014. URL: http://dx.doi.org/10.1007/s00453-012-9683-x.
  10. Camil Demetrescu, Mikkel Thorup, Rezaul Alam Chowdhury, and Vijaya Ramachandran. Oracles for distances avoiding a failed node or link. SIAM J. Comput., 37(5):1299-1318, 2008. URL: http://dx.doi.org/10.1137/S0097539705429847.
  11. 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.
  12. Fabrizio Grandoni and Virginia Vassilevska Williams. Improved distance sensitivity oracles via fast single-source replacement paths. In FOCS, pages 748-757, 2012. Google Scholar
  13. 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.
  14. 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
  15. Merav Parter. Dual failure resilient BFS structure. In PODC, pages 481-490, 2015. Google Scholar
  16. 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.
  17. Merav Parter and David Peleg. Fault tolerant approximate BFS structures. In SODA, pages 1073-1092, 2014. Google Scholar
  18. Christian Sommer. Shortest-path queries in static networks. ACM Comput. Surv., 46(4):45:1-45:31, 2014. URL: http://dx.doi.org/10.1145/2530531.
  19. Mikkel Thorup and Uri Zwick. Approximate distance oracles. J. ACM, 52(1):1-24, 2005. A preliminary version of this paper appeared in SODA'01. 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