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

DOI10.1137/1.9781611974782.28MaRDI QIDQ4575765zbMATH OpenOpenAlexFDO

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)

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

Mathematics Subject Classification ID

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

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}lo{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 $ildeO(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

• Worst-case update times for fully-dynamic all-pairs shortest paths
• Fully-Dynamic All-Pairs Shortest Paths: Improved Worst-Case Time and Space Bounds
• Average Update Times for Fully-Dynamic All-Pairs Shortest Paths
• Average update times for fully-dynamic all-pairs shortest paths
• scientific article; zbMATH DE number 2086658
• Fully dynamic all-pairs shortest paths: breaking the \(O(n)\) barrier
• A new approach to dynamic all pairs shortest paths
• Dynamic approximate all-pairs shortest paths in undirected graphs
• Algorithm Theory - SWAT 2004
• A new approach to dynamic all pairs shortest paths

Cited in

(15)

• Worst-case update times for fully-dynamic all-pairs shortest paths
• Dynamic matching: reducing integral algorithms to approximately-maximal fractional algorithms
• Algorithm Theory - SWAT 2004
• Reliable Hubs for Partially-Dynamic All-Pairs Shortest Paths in Directed Graphs
• scientific article; zbMATH DE number 2086658 (Why is no real title available?)
• Fully-Dynamic All-Pairs Shortest Paths: Improved Worst-Case Time and Space Bounds
• Single-Source Shortest Paths and Strong Connectivity in Dynamic Planar Graphs.
• Average Update Times for Fully-Dynamic All-Pairs Shortest Paths
• On the robustness of the metric dimension of grid graphs to adding a single edge
• A new approach to dynamic all pairs shortest paths
• Fully dynamic connectivity oracles under general vertex updates
• Single-source shortest paths and strong connectivity in dynamic planar graphs
• Average update times for fully-dynamic all-pairs shortest paths
• Deterministic incremental APSP with polylogarithmic update time and stretch
• Improved dynamic graph coloring

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)