Worst-case update times for fully-dynamic all-pairs shortest paths

ABSTRACT

We present here the first solution to the fully-dynamic all pairs shortest path problem where every update is faster than a recomputation from scratch in Ω(n³log ⁄n) time. This is for a directed graph with arbitrary non-negative edge weights. An update inserts or deletes a vertex with all incident edges. After each such vertex update, we update a complete distance matrix in Õ(n^2.75) time.

REFERENCES

• 1: G. M. Ade'lson-Velskiui and E. M. Landis. An algorithm for the organization of information. Dokladi Akademia Nauk SSSR, 146(2):1259--1262, 1962.
• 2: R. Bellman. On a routing problem. Quart. Appl. Math., 16(1):87--90, 1958.
• 3: Norbert Blum, On the single-operation worst-case time complexity of the disjoint set union problem, SIAM Journal on Computing, v.15 n.4, p.1021-1024, Nov. 1986 [doi>10.1137/0215072]
• 4: Gerth Stølting Brodal , George Lagogiannis , Christos Makris , Athanasios Tsakalidis , Kostas Tsichlas, Optimal finger search trees in the pointer machine, Journal of Computer and System Sciences, v.67 n.2, p.381-418, September 2003 [doi>10.1016/S0022-0000(03)00013-8]
• 5: C. Demetrescu , G. F. Italiano, Fully dynamic transitive closure: breaking through the O(n/sup 2/) barrier, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.381, November 12-14, 2000
• 6: 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]
• 7: 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
• 8: E. W. Dijkstra. A note on two problems in connexion with graphs. Numer. Math., 1:269--271, 1959.
• 9: David Eppstein , Zvi Galil , Giuseppe F. Italiano , Amnon Nissenzweig, Sparsification—a technique for speeding up dynamic graph algorithms, Journal of the ACM (JACM), v.44 n.5, p.669-696, Sept. 1997 [doi>10.1145/265910.265914]
• 10: Robert W. Floyd, Algorithm 97: Shortest path, Communications of the ACM, v.5 n.6, p.345, June 1962 [doi>10.1145/367766.368168]
• 11: L. R. Ford and D. R. Fulkerson. Flows in networks. Princeton University Press, 1962.
• 12: G. N. Frederickson. Data structures for on-line updating of minimum spanning trees, with applications. SIAM J. Computing, 14(4):781--798, 1985.
• 13: 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]
• 14: M.L. Fredman. New bounds on the complexity of the shortest path problem. SIAM J. Computing, 5(1):83--89, 1976.
• 15: M. Fredman , M. Saks, The cell probe complexity of dynamic data structures, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.345-354, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73040]
• 16: Robert Endre Tarjan, Efficiency of a Good But Not Linear Set Union Algorithm, Journal of the ACM (JACM), v.22 n.2, p.215-225, April 1975 [doi>10.1145/321879.321884]
• 17: Monika R. Henzinger , Valerie King, Randomized fully dynamic graph algorithms with polylogarithmic time per operation, Journal of the ACM (JACM), v.46 n.4, p.502-516, July 1999 [doi>10.1145/320211.320215]
• 18: Monika R. Henzinger , Valerie King, Maintaining Minimum Spanning Forests in Dynamic Graphs, SIAM Journal on Computing, v.31 n.2, p.364-374, 2001 [doi>10.1137/S0097539797327209]
• 19: Jacob Holm , Kristian de Lichtenberg , Mikkel Thorup, Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity, Journal of the ACM (JACM), v.48 n.4, p.723-760, July 2001 [doi>10.1145/502090.502095]
• 20: Valerie King, Fully Dynamic Algorithms for Maintaining All-Pairs Shortest Paths and Transitive Closure in Digraphs, Proceedings of the 40th Annual Symposium on Foundations of Computer Science, p.81, October 17-18, 1999
• 21: C. Levcopoulos , Mark H. Overmars, A balanced search tree with O(1) worst case update time, Acta Informatica, v.26 n.3, p.269-277, Nov. 1988 [doi>10.1007/BF00299635]
• 22: Liam Roditty, A faster and simpler fully dynamic transitive closure, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
• 23: Liam Roditty , Uri Zwick, Dynamic Approximate All-Pairs Shortest Paths in Undirected Graphs, Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS'04), p.499-508, October 17-19, 2004 [doi>10.1109/FOCS.2004.22]
• 24: Piotr Sankowski, Dynamic Transitive Closure via Dynamic Matrix Inverse (Extended Abstract), Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS'04), p.509-517, October 17-19, 2004 [doi>10.1109/FOCS.2004.25]
• 25: M. Thorup. Fully-dynamic all-pairs shortest paths: faster and allowing negative cycles. In Proc. 9th SWAT, pages 384--396, 2004.
• 26: Stephen Warshall, A Theorem on Boolean Matrices, Journal of the ACM (JACM), v.9 n.1, p.11-12, Jan. 1962 [doi>10.1145/321105.321107]
• 27: Dan E. Willard , George S. Lueker, Adding range restriction capability to dynamic data structures, Journal of the ACM (JACM), v.32 n.3, p.597-617, July 1985 [doi>10.1145/3828.3839]
• 28: J. W. J. Williams. Algorithm 232. Comm. ACM, 7(6):347--348, 1964.

INDEX TERMS

Primary Classification:
  E. Data
  E.1 DATA STRUCTURES
      Subjects: Graphs and networks

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

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

General Terms:
Algorithms

Keywords:
dynamic graph algorithms, shortest paths, worst-case update times