Fully dynamic all pairs shortest paths with real edge weights
- 1 January 2001
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 260-267
- https://doi.org/10.1109/sfcs.2001.959900
Abstract
We present the first fully dynamic algorithm for maintaining all pairs shortest paths in directed graphs with real-valued edge weights. Given a dynamic directed graph G such that each edge can assume at most S different real values, we show how to support updates deterministically in O(S/spl middot/n/sup 2.5/log/sup 3/n) amortized time and queries in optimal worst-case time. No previous fully dynamic algorithm was known for this problem. In the special case where edge weights can only be increased, we give a randomized algorithm with one-sided error which supports updates faster in O(S/spl middot/nlog/sup 3/n) amortized time.Keywords
This publication has 20 references indexed in Scilit:
- A dynamization of the All Pairs Least Cost Path ProblemPublished by Springer Nature ,2005
- Fully Dynamic Algorithms for Maintaining Shortest Paths TreesJournal of Algorithms, 2000
- Faster Shortest-Path Algorithms for Planar GraphsJournal of Computer and System Sciences, 1997
- An Incremental Algorithm for a Generalization of the Shortest-Path ProblemJournal of Algorithms, 1996
- On the computational complexity of dynamic graph problemsTheoretical Computer Science, 1996
- On the All-Pairs-Shortest-Path Problem in Unweighted Undirected GraphsJournal of Computer and System Sciences, 1995
- A new upper bound on the complexity of the all pairs shortest path problemInformation Processing Letters, 1992
- Incremental algorithms for minimal length pathsJournal of Algorithms, 1991
- Matrix multiplication via arithmetic progressionsJournal of Symbolic Computation, 1990
- Fibonacci heaps and their uses in improved network optimization algorithmsJournal of the ACM, 1987