hide
Free keywords:
Computer Science, Data Structures and Algorithms, cs.DS
Abstract:
We revisit the classic problem of dynamically maintaining shortest paths
between all pairs of nodes of a directed weighted graph. The allowed updates
are insertions and deletions of nodes and their incident edges. We give
worst-case guarantees on the time needed to process a single update (in
contrast to related results, the update time is not amortized over a sequence
of updates).
Our main result is a simple randomized algorithm that for any parameter $c>1$
has a worst-case update time of $O(cn^{2+2/3} \log^{4/3}{n})$ and answers
distance queries correctly with probability $1-1/n^c$, against an adaptive
online adversary if the graph contains no negative cycle. The best
deterministic algorithm is by Thorup [STOC 2005] with a worst-case update time
of $\tilde O(n^{2+3/4})$ and assumes non-negative weights. This is the first
improvement for this problem for more than a decade. Conceptually, our
algorithm shows that randomization along with a more direct approach can
provide better bounds.
