Dynamic Approximate All-Pairs Shortest Paths in Undirected Graphs
Authors:
- Liam RodittyLRLiam Roditty
- Uri ZwickUZUri Zwick
- 1 January 2012
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 41 (3) , 670-683
Abstract
We obtain three new dynamic algorithms for the approximate all-pairs shortest paths problem in unweighted undirected graphs: (i) For any fixed $\varepsilon>0$, a decremental algorithm with an expected total running time of $\tilde{O}(mn)$, where $m$ is the number of edges and $n$ is the number of vertices in the initial graph. Each distance query is answered in $O(1)$ worst-case time, and the stretch of the returned distances is at most $1+\varepsilon$. The algorithm uses $\tilde{O}(n^2)$ space. (ii) For any fixed integer $k\geq1$, a decremental algorithm with an expected total running time of $\tilde{O}(mn)$. Each query is answered in $O(1)$ worst-case time, and the stretch of the returned distances is at most $2k-1$. This algorithm, however, uses only $O(m+n^{1+1/k})$ space. It is obtained by dynamizing techniques of Thorup and Zwick. In addition to being more space efficient, this algorithm is also one of the building blocks used to obtain the first algorithm. (iii) For any fixed $\varepsilon,\delta>0$ and every $t\leq m^{1/2-\delta}$, a fully dynamic algorithm with an expected amortized update time of $\tilde{O}(mn/t)$ and worst-case query time of $O(t)$. The stretch of the returned distances is at most $1+\varepsilon$. All algorithms can also be made to work on undirected graphs with small integer edge weights. If the largest edge weight is $b$, then all bounds on the running times are multiplied by $b$.
Keywords
This publication has 24 references indexed in Scilit:
- Improved decremental algorithms for maintaining transitive closure and all-pairs shortest pathsJournal of Algorithms, 2007
- Experimental analysis of dynamic all pairs shortest path algorithmsACM Transactions on Algorithms, 2006
- A new approach to dynamic all pairs shortest pathsJournal of the ACM, 2004
- All-Pairs Small-Stretch PathsJournal of Algorithms, 2001
- Fast Estimation of Diameter and Shortest Paths (Without Matrix Multiplication)SIAM Journal on Computing, 1999
- Near-Linear Time Construction of Sparse Neighborhood CoversSIAM Journal on Computing, 1998
- Fast Algorithms for Constructing t-Spanners and Paths with Stretch tSIAM Journal on Computing, 1998
- Dynamic Perfect Hashing: Upper and Lower BoundsSIAM Journal on Computing, 1994
- On-line computation of minimal and maximal length pathsTheoretical Computer Science, 1992
- Incremental algorithms for minimal length pathsJournal of Algorithms, 1991