A New Deterministic Algorithm for Fully Dynamic All-Pairs Shortest Paths
share
We study the fully dynamic All-Pairs Shortest Paths (APSP) problem in undirected edge-weighted graphs. Given an n-vertex graph G with non-negative edge lengths, that undergoes an online sequence of edge insertions and deletions, the goal is to support approximate distance queries and shortest-path queries. We provide a deterministic algorithm for this problem, that, for a given precision parameter ϵ, achieves approximation factor (loglog n)^2^O(1/ϵ^3), and has amortized update time O(n^ϵlog L) per operation, where L is the ratio of longest to shortest edge length. Query time for distance-query is O(2^O(1/ϵ)·log n·loglog L), and query time for shortest-path query is O(|E(P)|+2^O(1/ϵ)·log n·loglog L), where P is the path that the algorithm returns. To the best of our knowledge, even allowing any o(n)-approximation factor, no adaptive-update algorithms with better than Θ(m) amortized update time and better than Θ(n) query time were known prior to this work. We also note that our guarantees are stronger than the best current guarantees for APSP in decremental graphs in the adaptive-adversary setting.
READ FULL TEXT