Abstract
We obtain the following results related to dynamic versions of the shortest-paths problem:
(i). Reductions that show that the incremental and decremental single-source shortest-paths problems, for weighted directed or undirected graphs, are, in a strong sense, at least as hard as the static all-pairs shortest-paths problem. We also obtain slightly weaker results for the corresponding unweighted problems.
(ii). A randomized fully-dynamic algorithm for the all-pairs shortest-paths problem in directed unweighted graphs with an amortized update time of \(\tilde{O}(m\sqrt n)\) and a worst case query time is O(n 3/4).
(iii). A deterministic O(n 2log n) time algorithm for constructing a (log n)-spanner with O(n) edges for any weighted undirected graph on n vertices. The algorithm uses a simple algorithm for incrementally maintaining single-source shortest-paths tree up to a given distance.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Althöfer, I., Das, G., Dobkin, D., Joseph, D., Soares, J.: On sparse spanners of weighted graphs. Discrete & Computational Geometry 9, 81–100 (1993)
Baswana, S., Hariharan, R., Sen, S.: Improved decremental algorithms for transitive closure and all-pairs shortest paths. In: Proc. of 34th STOC, pp. 117–123 (2002)
Baswana, S., Hariharan, R., Sen, S.: Maintaining all-pairs approximate shortest paths under deletion of edges. In: Proc. of 14th SODA, pp. 394–403 (2003)
Baswana, S., Sen, S.: A simple linear time algorithm for computing (2k – 1)- spanner of O(n 1 + 1/k) size for weighted graphs. In: Baeten, J.C.M., Lenstra, J.K., Parrow, J., Woeginger, G.J. (eds.) ICALP 2003. LNCS, vol. 2719, pp. 384–396. Springer, Heidelberg (2003)
Chan, T.: Dynamic subgraph connectivity with geometric applications. In: Proc. of 34th STOC, pp. 7–13 (2002)
Chandra, B., Das, G., Narasimhan, G., Soares, J.: New sparseness results on graph spanners. Internat. J. Comput. Geom. Appl. 5, 125–144 (1995)
Coppersmith, D., Winograd, S.: Matrix multiplication via arithmetic progressions. Journal of Symbolic Computation 9, 251–280 (1990)
Demetrescu, C., Italiano, G.: A new approach to dynamic all pairs shortest paths. In: Proc. of 35th STOC, pp. 159–166 (2003)
Even, S., Shiloach, Y.: An on-line edge-deletion problem. Journal of the ACM 28(1), 1–4 (1981)
Fredman, M., Tarjan, R.: Fibonacci heaps and their uses in improved network optimization algorithms. Journal of the ACM 34, 596–615 (1987)
Galil, Z., Margalit, O.: All pairs shortest distances for graphs with small integer length edges. Information and Computation 134, 103–139 (1997)
Gudmundsson, J., Levcopoulos, C., Narasimhan, G.: Fast greedy algorithm for constructing sparse geometric spanners. SIAM J. Comput. 31, 1479–1500 (2002)
Hagerup, T.: Improved shortest paths on the word RAM. In: Welzl, E., Montanari, U., Rolim, J.D.P. (eds.) ICALP 2000. LNCS, vol. 1853, pp. 61–72. Springer, Heidelberg (2000)
Henzinger, M., King, V.: Fully dynamic biconnectivity and transitive closure. In: Proc. of 36th FOCS, pp. 664–672 (1995)
Karger, D., Koller, D., Phillips, S.: Finding the hidden path: time bounds for all-pairs shortest paths. SIAM Journal on Computing 22, 1199–1217 (1993)
Peleg, D., Schäffer, A.: Graph spanners. J. Graph Theory 13, 99–116 (1989)
Pettie, S.: A new approach to all-pairs shortest paths on real-weighted graphs. Theoretical Computer Science 312(1), 47–74 (2004)
Pettie, S., Ramachandran, V.: Computing shortest paths with comparisons and additions. In: Proc. of 13th SODA, pp. 267–276 (2002)
Ramalingam, G., Reps, T.: An incremental algorithm for a generalization of the shortest-path problem. Journal of Algorithms 21(2), 267–305 (1996)
Roditty, L., Zwick, U.: Improved dynamic reachability algorithms for directed graphs. In: Proc. of 43rd FOCS, pp. 679–688 (2002)
Roditty, L., Zwick, U.: A fully dynamic reachability algorithm for directed graphs with an almost linear update time. In: Proc. of 36th STOC, pp. 184–191 (2004)
Roditty, L., Zwick, U.: Dynamic approximate all-pairs shortest paths in undirected graphs. In: Proc. of 45th FOCS (2004) (to appear)
Seidel, R.: On the all-pairs-shortest-path problem in unweighted undirected graphs. J. Comput. Syst. Sci. 51, 400–403 (1995)
Shoshan, A., Zwick, U.: All pairs shortest paths in undirected graphs with integer weights. In: Proc. of 40th FOCS, pp. 605–614 (1999)
Thorup, M.: Undirected single-source shortest paths with positive integer weights in linear time. Journal of the ACM 46, 362–394 (1999)
Thorup, M.: Fully-dynamic all-pairs shortest paths: Faster and allowing negative cycles. In: Hagerup, T., Katajainen, J. (eds.) SWAT 2004. LNCS, vol. 3111, pp. 384–396. Springer, Heidelberg (2004) (to appear)
Thorup, M., Zwick, U.: Approximate distance oracles. In: Proc. of 33rd STOC, pp. 183–192 (2001); Full version to appear in the Journal of the ACM
Ullman, J., Yannakakis, M.: High-probability parallel transitive-closure algorithms. SIAM Journal on Computing 20, 100–125 (1991)
Yuster, R., Zwick, U.: Fast sparse matrix multiplication. In: Albers, S., Radzik, T. (eds.) ESA 2004. LNCS, vol. 3221, pp. 604–615. Springer, Heidelberg (2004)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2004 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Roditty, L., Zwick, U. (2004). On Dynamic Shortest Paths Problems. In: Albers, S., Radzik, T. (eds) Algorithms – ESA 2004. ESA 2004. Lecture Notes in Computer Science, vol 3221. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-30140-0_52
Download citation
DOI: https://doi.org/10.1007/978-3-540-30140-0_52
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-23025-0
Online ISBN: 978-3-540-30140-0
eBook Packages: Springer Book Archive