Fully dynamic all-pairs shortest paths with worst-case update-time revisited

Paths and cycles (05C38) Graph theory (including graph drawing) in computer science (68R10) Randomized algorithms (68W20) Analysis of algorithms (68W40)

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 (c n^{2 + 2 / 3} l o g^{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

i l d e 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.

Recommendations

Cited in

(17)

This page was built for publication: Fully dynamic all-pairs shortest paths with worst-case update-time revisited

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4575765)