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

DOI10.1137/1.9781611974782.28zbMATH Open1410.68267arXiv1607.05132OpenAlexW2949477394MaRDI QIDQ4575765FDOQ4575765

Authors: Ittai Abraham, Shiri Chechik, Sebastian Krinninger

Publication date: 16 July 2018

Published in: Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1607.05132

Recommendations

Mathematics Subject Classification ID

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

Cited In (15)

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)