research-article

A nearly optimal oracle for avoiding failed vertices and edges

Authors:

Aaron Bernstein,

David KargerAuthors Info & Claims

STOC '09: Proceedings of the forty-first annual ACM symposium on Theory of computing

Pages 101 - 110

https://doi.org/10.1145/1536414.1536431

Published: 31 May 2009 Publication History

Get Access

Abstract

We present an improved oracle for the distance sensitivity problem. The goal is to preprocess a directed graph G = (V,E) with non-negative edge weights to answer queries of the form: what is the length of the shortest path from x to y that does not go through some failed vertex or edge f. The previous best algorithm produces an oracle of size ~O(n²) that has an O(1) query time, and an ~O(n²√m) construction time. It was a randomized Monte Carlo algorithm that worked with high probability. Our oracle also has a constant query time and an ~O(n²) space requirement, but it has an improved construction time of ~O(mn), and it is deterministic. Note that O(1) query, O(n²) space, and O(mn) construction time is also the best known bound (up to logarithmic factors) for the simpler problem of finding all pairs shortest paths in a weighted, directed graph. Thus, barring improved solutions to the all pairs shortest path problem, our oracle is optimal up to logarithmic factors.

References

[1]

.O. Ball, B.L. Golden, and R.V. Vohra. Finding the most vital arcs in a network. Operations Research Letters, 8:73--76, 1989.

Digital Library

Google Scholar

[2]

. Bar--Noy, S. Khuller, and B. Schieber. The complexity of finding most vital arcs and nodes. Technical Report No CS-TR-3539, Institute for Advanced Studies, University of Maryland, College Park, MD, 1995.

Google Scholar

[3]

.Berkman and U.Vishkin. Recursive star-tree parallel data structure. SIAM Journal of Computing, 22(2):221--242, 1993.

Digital Library

Google Scholar

[4]

. Bernstein and D. Karger. Improved distance sensitivity oracles via random sampling. In Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '08), San Francisco, California, pages 34--43, 2008.

Digital Library

Google Scholar

[5]

.A. Chowdhury and V. Ramach. Improved distance oracles for avoiding link-failure. In Proc. of the 13th International Symposium on Algorithms and Computation (ISAAC '02), Vancouver, Canada, LNCS 2518, pages 523--534, 2002.

Digital Library

Google Scholar

[6]

. Demetrescu, M. Thorup, R.A. Chowdhury, and V. Ramachandran. Oracles for distances avoiding a node or link failure. SIAM Journal of computing, 37(5):1299--1318, 2008.

Digital Library

Google Scholar

[7]

.Dijkstra. A note on two problems in connexion with graphs. Numerische Mathematik, 1:269--271, 1959.

Digital Library

Google Scholar

[8]

. Emek, D. Peleg, and L. Roditty. A near-linear time algorithm for computing replacement paths in planar directed graphs. In Proc. of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '08), San Francisco, California, pages 428--435, 2008.

Digital Library

Google Scholar

[9]

.Harel and R.E.Tarjan. Fast algorithms for finding nearest common ancestors. SIAM Journal of Computing, 13(2):338--355, 1984.

Digital Library

Google Scholar

[10]

.Hershberger and S.Suri. Vickrey prices and shortest paths: what is an edge worth?. In Proceedings of the 42nd IEEE Annual Symposium on Foundations of Computer Science (FOCS '01), Las Vegas, Nevada, pages 129--140, 2001. Erratum in FOCS '02.

Digital Library

Google Scholar

[11]

. Hershberger, S. Suri, and A. Bhosle. On the difficulty of some shortest path problems. In Proc. of the 20th International Symposium of Theoretical Aspects of Computer Science (STACS'03), Berlin, Germany, pages 343--354, 2003.

Digital Library

Google Scholar

[12]

. King. Fully dynamic algorithms for maintaining all-pairs shortest paths and transitive closure in digraphs. Proceedings of the 40th IEEE Annual Symposium on Foundations of Computer Science (FOCS '99), New York, NY, pages 81--89, 1999.

Digital Library

Google Scholar

[13]

. Roditty and U. Zwick. Replacement Paths and k Simple Shortest Paths in Unweighted Directed Graphs. In Proc. of the 32nd International Colloquium on Automata, Languages and Programming, Lisboa, Portugal, pages 249--260, 2005.

Digital Library

Google Scholar

Cited By

View all

Dey DGupta MMohar BShinkar IO'Donnell R(2024)Nearly Optimal Fault Tolerant Distance OracleProceedings of the 56th Annual ACM Symposium on Theory of Computing10.1145/3618260.3649697(944-955)Online publication date: 10-Jun-2024
https://dl.acm.org/doi/10.1145/3618260.3649697
Bilò DChechik SChoudhary KCohen SFriedrich TSchirneck M(2024)Improved Distance (Sensitivity) Oracles with Subquadratic Space2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS61266.2024.00097(1550-1558)Online publication date: 27-Oct-2024
https://doi.org/10.1109/FOCS61266.2024.00097
Izumi TEmek YWadayama TMasuzawa T(2024)Deterministic fault-tolerant connectivity labeling schemeDistributed Computing10.1007/s00446-024-00472-638:1(31-50)Online publication date: 4-Nov-2024
https://doi.org/10.1007/s00446-024-00472-6
Show More Cited By

Index Terms

A nearly optimal oracle for avoiding failed vertices and edges
1. Theory of computation
  1. Design and analysis of algorithms

Recommendations

Oracles for Distances Avoiding a Failed Node or Link

We consider the problem of preprocessing an edge-weighted directed graph $G$ to answer queries that ask for the length and first hop of a shortest path from any given vertex $x$ to any given vertex $y$ avoiding any given vertex or edge. As a natural ...
An optimal algorithm for shortest paths on weighted interval and circular-arc graphs, with applications

We give the first linear-time algorithm for computing single-source shortest paths in a weighted interval or circular-arc graph, when we are given the model of that graph, i.e., the actual weighted intervals or circular-arcsand the sorted list of the ...
(Nearly) sample-optimal sparse Fourier transform
SODA '14: Proceedings of the twenty-fifth annual ACM-SIAM symposium on Discrete algorithms

We consider the problem of computing a k-sparse approximation to the discrete Fourier transform of an n-dimensional signal. Our main result is a randomized algorithm that computes such an approximation using O(k log n(log log n)^O(1)) signal samples in ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

STOC '09: Proceedings of the forty-first annual ACM symposium on Theory of computing

May 2009

750 pages

ISBN:9781605585062

DOI:10.1145/1536414

Program Chair:
Michael Mitzenmacher
Harvard University

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 31 May 2009

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

STOC '09

Sponsor:

STOC '09: Symposium on Theory of Computing

May 31 - June 2, 2009

MD, Bethesda, USA

Acceptance Rates

Overall Acceptance Rate 1,469 of 4,586 submissions, 32%

Upcoming Conference

STOC '25

Sponsor:
sigact

57th Annual ACM Symposium on Theory of Computing (STOC 2025)

June 23 - 27, 2025

Prague , Czech Republic

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

76
Total Citations
View Citations
537
Total Downloads

Downloads (Last 12 months)17
Downloads (Last 6 weeks)3

Reflects downloads up to 01 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Dey DGupta MMohar BShinkar IO'Donnell R(2024)Nearly Optimal Fault Tolerant Distance OracleProceedings of the 56th Annual ACM Symposium on Theory of Computing10.1145/3618260.3649697(944-955)Online publication date: 10-Jun-2024
https://dl.acm.org/doi/10.1145/3618260.3649697
Bilò DChechik SChoudhary KCohen SFriedrich TSchirneck M(2024)Improved Distance (Sensitivity) Oracles with Subquadratic Space2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS61266.2024.00097(1550-1558)Online publication date: 27-Oct-2024
https://doi.org/10.1109/FOCS61266.2024.00097
Izumi TEmek YWadayama TMasuzawa T(2024)Deterministic fault-tolerant connectivity labeling schemeDistributed Computing10.1007/s00446-024-00472-638:1(31-50)Online publication date: 4-Nov-2024
https://doi.org/10.1007/s00446-024-00472-6
Jeong DGunby-Mann ACohen SKatzmann MPham CBhakta AFriedrich TChin P(2024)Deep Distance Sensitivity OraclesComplex Networks & Their Applications XII10.1007/978-3-031-53468-3_38(452-463)Online publication date: 20-Feb-2024
https://doi.org/10.1007/978-3-031-53468-3_38
Baswana SBhanja KPandey A(2023)Minimum+1 (s, t)-cuts and Dual-edge Sensitivity OracleACM Transactions on Algorithms10.1145/362327119:4(1-41)Online publication date: 14-Oct-2023
https://dl.acm.org/doi/10.1145/3623271
Izumi TEmek YWadayama TMasuzawa TOshman RNolin AHalldorsson MBalliu A(2023)Deterministic Fault-Tolerant Connectivity Labeling SchemeProceedings of the 2023 ACM Symposium on Principles of Distributed Computing10.1145/3583668.3594584(190-199)Online publication date: 19-Jun-2023
https://dl.acm.org/doi/10.1145/3583668.3594584
Bilò DChechik SChoudhary KCohen SFriedrich TKrogmann SSchirneck MSaha BServedio R(2023)Approximate Distance Sensitivity Oracles in Subquadratic SpaceProceedings of the 55th Annual ACM Symposium on Theory of Computing10.1145/3564246.3585251(1396-1409)Online publication date: 2-Jun-2023
https://dl.acm.org/doi/10.1145/3564246.3585251
Karczmarz ASankowski P(2023)Sensitivity and Dynamic Distance Oracles via Generic Matrices and Frobenius Form2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS57990.2023.00106(1745-1756)Online publication date: 6-Nov-2023
https://doi.org/10.1109/FOCS57990.2023.00106
Bilò DChoudhary KCohen SFriedrich TKrogmann SSchirneck M(2023)Compact Distance Oracles with Large Sensitivity and Low StretchAlgorithms and Data Structures10.1007/978-3-031-38906-1_11(149-163)Online publication date: 28-Jul-2023
https://doi.org/10.1007/978-3-031-38906-1_11
Duan RRen HLeonardi SGupta A(2022)Maintaining exact distances under multiple edge failuresProceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing10.1145/3519935.3520002(1093-1101)Online publication date: 9-Jun-2022
https://dl.acm.org/doi/10.1145/3519935.3520002
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Abstract

References

Cited By

Index Terms

Recommendations

Oracles for Distances Avoiding a Failed Node or Link

An optimal algorithm for shortest paths on weighted interval and circular-arc graphs, with applications

(Nearly) sample-optimal sparse Fourier transform

Comments

Information

Published In

Sponsors

Publisher

Publication History

Permissions

Check for updates

Author Tags

Qualifiers

Conference

Acceptance Rates

Upcoming Conference

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

Login options

Full Access

View options

PDF

eReader

Share

Share this Publication link

Share on social media

Affiliations