Abstract
We examine several structural properties of single-source shortest paths and present a local search algorithm for the partially dynamic single-source shortest paths problem. Our algorithm works on both deterministic digraphs and undirected graphs. For a deterministic digraph with positive arc weights, our algorithm handles a single arc weight increase in \(O(n+\frac{n^2\log n}{m})\) expected time, where n is the number of nodes and m is the number of edges in the digraph. Specifically, our algorithm is an O(n) expected time algorithm when m = Ω(nlogn). This solves partially an open problem proposed by Demetrescu and Italiano (Journal of the ACM. 51(2004), 968–992).
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
Ausiello, G., Italiano, G.F., Marchetti-Spaccamela, A., Nanni, U.: Incremental algorithms for minimal length paths. Journal of Algorithms 12, 615–638 (1991)
Bernstein, A.: Fully dynamic (2 + ε) approximate all-pairs shortest paths with fast query and close to linear update time. In: Proc. of 50th FOCS, pp. 693–702 (2009)
Bernstein, A., Roditty, L.: Improved dynamic algorithms for maintaining approximate shortest paths under deletions. In: Proc. of 22th SODA, pp. 1355–1365 (2011)
Demetrescu, C., Italiano, G.F.: A new approach to dynamic all pairs shortest paths. Journal of the ACM 51, 968–992 (2004)
Demetrescu, C., Italiano, G.F.: Experimental analysis of dynamic all pairs shortest path algorithms. ACM Transactions on Algorithms 2, 578–601 (2006)
Dijkstra, E.W.: A note on two problems in connection with graphs. Numerische Mathematik 1, 269–271 (1959)
Dinitz, Y.: Dinitz’ algorithm: The original version and Even’s version. In: Essays in Memory of Shimon Even, pp. 218–240 (2006)
Even, S., Shiloach, Y.: An on-line edge-deletion problem. Journal of the ACM 28, 1–4 (1981)
Fakcharoemphol, J., Rao, S.: Planar graphs, negative weight edges, shortest paths, and near linear time. In: Proc. of 42nd FOCS, pp. 232–241 (2001)
Friedrich, T., Hebbinghaus, N.: Average update times for fully-dynamic all-pairs shortest paths. In: Hong, S.-H., Nagamochi, H., Fukunaga, T. (eds.) ISAAC 2008. LNCS, vol. 5369, pp. 692–703. Springer, Heidelberg (2008)
King, V.: Fully dynamic algorithms for maintaining all-pairs shortest paths and transitive closure in digraphs. In: Proc. of 40th FOCS, pp. 81–99 (1999)
Murchland, J.: The effect of increasing or decreasing the length of a single arc on all shortest distances in a graph. Technical report, LBS-TNT-26. London Business School, Transport Network Theory Unit, London, UK (1967)
Peres, Y., Sotnikov, D., Sudakov, B., Zwick, U.: All-pairs shortest paths in O(n 2) time with high probability. In: Proc. of 51th FOCS, pp. 663–672 (2010)
Roditty, L., Zwick, U.: Dynamic approximate all-pairs shortest paths in undirected graphs. In: Proc. of 45th FOCS, pp. 499–508 (2004)
Roditty, L., Zwick, U.: On dynamic shortest paths problems. In: Albers, S., Radzik, T. (eds.) ESA 2004. LNCS, vol. 3221, pp. 580–591. Springer, Heidelberg (2004)
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)
Thorup, M.: Worst-case update times for fully-dynamic all-pairs shortest paths. In: Proc. of 37th STOC, pp. 112–119 (2005)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer International Publishing Switzerland
About this paper
Cite this paper
Ding, W., Lin, G. (2014). Partially Dynamic Single-Source Shortest Paths on Digraphs with Positive Weights. In: Gu, Q., Hell, P., Yang, B. (eds) Algorithmic Aspects in Information and Management. AAIM 2014. Lecture Notes in Computer Science, vol 8546. Springer, Cham. https://doi.org/10.1007/978-3-319-07956-1_18
Download citation
DOI: https://doi.org/10.1007/978-3-319-07956-1_18
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-07955-4
Online ISBN: 978-3-319-07956-1
eBook Packages: Computer ScienceComputer Science (R0)