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

Preprint · Ittai Abraham, Shiri Chechik, Sebastian Krinninger

- Archive id: arxiv:1607.05132
- Published: 2016-07-18
- DOI: https://doi.org/10.1137/1.9781611974782.28
- arXiv: https://arxiv.org/abs/1607.05132
- Source URL: https://arxiv.org/abs/1607.05132
- PDF: https://arxiv.org/pdf/1607.05132
- Provenance: arxiv

## 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.

_Abstract reproduced under CC0-1.0 (arXiv descriptive metadata)._

---
Space Kitty Archive · https://space-kitty.com · API: https://space-kitty.com/api/v1 · MCP: https://space-kitty.com/mcp · Premium: $0.20/request via x402 (Base Sepolia (testnet)). Metadata: arXiv (CC0), OpenAlex (CC0), Europe PMC (CC BY/CC0 works), ClinicalTrials.gov.