Fully dynamic (2 + ε) approximate all-pairs shortest paths with fast query and close to linear update time
Author:
- Aaron BernsteinABAaron Bernstein
- 1 October 2009
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 02725428,p. 693-702
Abstract
For any fixed 1 > ¿ > 0 we present a fully dynamic algorithm for maintaining (2 + ¿)-approximate all-pairs shortest paths in undirected graphs with positive edge weights. We use a randomized (Las Vegas) update algorithm (but a deterministic query procedure), so the time given is the expected amortized update time. Our query time O(log log log n). The update time is O¿(mn O(1/¿(log n)) log (nR)), where R is the ratio between the heaviest and the lightest edge weight in the graph (so R = 1 in unweighted graphs). Unfortunately, the update time does have the drawback of a super-polynomial dependence on e. it grows as (3/¿) (¿(log n/log(3/¿)) ) = n (¿(log(3/¿)/log n)) . Our algorithm has a significantly faster update time than any other algorithm with sub-polynomial query time. For exact distances, the state of the art algorithm has an update time of O¿(n 2 ). For approximate distances, the best previous algorithm has a O(kmn 1/k ) update time and returns (2 k - 1) stretch paths. Thus, it needs an update time of O(m¿(n)) to get close to our approximation, and it has to return O(¿(log n)) approximate distances to match our update time.Keywords
This publication has 6 references indexed in Scilit:
- Spanners and emulators with sublinear distance errors2006
- Approximate distance oraclesJournal of the ACM, 2005
- Dynamic Approximate All-Pairs Shortest Paths in Undirected Graphs2004
- A new approach to dynamic all pairs shortest pathsJournal of the ACM, 2004
- Fully dynamic algorithms for maintaining all-pairs shortest paths and transitive closure in digraphs2003
- An On-Line Edge-Deletion ProblemJournal of the ACM, 1981