Improved distance sensitivity oracles via random sampling

Aaron Bernstein, David Karger

Research output: Chapter in Book/Report/Conference proceedingConference contribution

30 Scopus citations

Abstract

We present improved oracles for the distance sensitivity problem. The goal is to preprocess a graph G = (V,E) with non-negative edge weights to answer queries of the form: what is the length of the shortest path from × to y that does not go through some failed vertex or edge f. There are two state of the art algorithms for this problem. The first produces an oracle of size Õ(n 2) that has an O(1) query time, and an Õ(mn 2) construction time. The second oracle has size O(n 2.5), but the construction time is only Õ(mn 1.5). We present two new oracles that substantially improve upon both of these results. Both oracles are constructed with randomized, Monte Carlo algorithms. For directed graphs with non-negative edge weights, we present an oracle of size Õ(n 2), which has an O(1) query time, and an Õ(n 2 √m) construction time. For unweighted graphs, we achieve a more general construction time of Õ(√n 3 · APSP + mn), where APSP is the time it takes to compute all pairs shortest paths in an aribtrary subgraph of G.

Original languageEnglish (US)
Title of host publicationProceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms
Pages34-43
Number of pages10
StatePublished - 2008
Externally publishedYes
Event19th Annual ACM-SIAM Symposium on Discrete Algorithms - San Francisco, CA, United States
Duration: Jan 20 2008Jan 22 2008

Publication series

NameProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

Other

Other19th Annual ACM-SIAM Symposium on Discrete Algorithms
CountryUnited States
CitySan Francisco, CA
Period1/20/081/22/08

All Science Journal Classification (ASJC) codes

  • Software
  • Mathematics(all)

Fingerprint Dive into the research topics of 'Improved distance sensitivity oracles via random sampling'. Together they form a unique fingerprint.

Cite this