TY - GEN

T1 - Improved distance sensitivity oracles via random sampling

AU - Bernstein, Aaron

AU - Karger, David

PY - 2008

Y1 - 2008

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=58449120261&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=58449120261&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:58449120261

SN - 9780898716474

T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

SP - 34

EP - 43

BT - Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms

T2 - 19th Annual ACM-SIAM Symposium on Discrete Algorithms

Y2 - 20 January 2008 through 22 January 2008

ER -