Improved distance sensitivity oracles via random sampling

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 x 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²) that has an O(1) query time, and an Õ(mn²) 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²), which has an O(1) query time, and an Õ(n²√m) construction time. For unweighted graphs, we achieve a more general construction time of Õ(√n³ · APSP + mn), where APSP is the time it takes to compute all pairs shortest paths in an aribtrary subgraph of G.

REFERENCES

• 1: G. Apostolopoulos , S. Kama , D. Williams , R. Guerin , A. Orda , T. Przygienda, QoS Routing Mechanisms and OSPF Extensions, RFC Editor, 1999
• 2: Omer Berkman , Uzi Vishkin, Recursive star-tree parallel data structure, SIAM Journal on Computing, v.22 n.2, p.221-242, April 1993 [doi>10.1137/0222017]
• 3: H. Chernoff. A measure of the asymptotic efficiency for tests of a hypothesis based on the sum of observations. Ann. Math. Stat, 23, 493509, 1952.
• 4: Camil Demetrescu , Giuseppe F. Italiano, A new approach to dynamic all pairs shortest paths, Journal of the ACM (JACM), v.51 n.6, p.968-992, November 2004 [doi>10.1145/1039488.1039492]
• 5: Camil Demetrescu , Mikkel Thorup, Oracles for distances avoiding a link-failure, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.838-843, January 06-08, 2002, San Francisco, California
• 6: Camil Demetrescu , Mikkel Thorup, Oracles for distances avoiding a link-failure, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.838-843, January 06-08, 2002, San Francisco, California
• 7: Michael L. Fredman , Robert Endre Tarjan, Fibonacci heaps and their uses in improved network optimization algorithms, Journal of the ACM (JACM), v.34 n.3, p.596-615, July 1987 [doi>10.1145/28869.28874]
• 8: Donald E. Knuth , Daniel H. Greene, Mathematics for the Analysis of Algorithms, Birkhauser Boston, 1999
• 9: Dov Harel , Robert Endre Tarjan, Fast algorithms for finding nearest common ancestors, SIAM Journal on Computing, v.13 n.2, p.338-355, May 1984 [doi>10.1137/0213024]
• 10: J. Hershberger , S. Suri, Vickrey Prices and Shortest Paths: What is an Edge Worth?, Proceedings of the 42nd IEEE symposium on Foundations of Computer Science, p.252, October 14-17, 2001

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Path and circuit problems

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.3 Complexity Measures and Classes

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms

General Terms:
Algorithms, Design, Theory