TY - GEN

T1 - Fully dynamic (2 + ∈) approximate all-pairs shortest paths with fast query and close to linear update time

AU - Bernstein, Aaron

PY - 2009

Y1 - 2009

N2 - For any fixed 1 > e > 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 Õ(mnO(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 ∈: 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 Õ(n2). For approximate distances, the best previous algorithm has a O(kmn1/k) update time and returns (2k-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.

AB - For any fixed 1 > e > 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 Õ(mnO(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 ∈: 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 Õ(n2). For approximate distances, the best previous algorithm has a O(kmn1/k) update time and returns (2k-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.

KW - Approximation algorithms

KW - Dynamic algorithms

KW - Graph algorithms

KW - Shortest paths

UR - http://www.scopus.com/inward/record.url?scp=77952384657&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=77952384657&partnerID=8YFLogxK

U2 - 10.1109/FOCS.2009.16

DO - 10.1109/FOCS.2009.16

M3 - Conference contribution

AN - SCOPUS:77952384657

SN - 9780769538501

T3 - Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS

SP - 693

EP - 702

BT - Proceedings - 50th Annual Symposium on Foundations of Computer Science, FOCS 2009

T2 - 50th Annual Symposium on Foundations of Computer Science, FOCS 2009

Y2 - 25 October 2009 through 27 October 2009

ER -