Fully Dynamic Shortest Paths in Sparse Digraphs
Lists
Only you see this
Abstract
We study the exact fully dynamic shortest paths problem. For real-weighted directed graphs, we show a deterministic fully dynamic data structure with $\tilde{O}(mn^{4/5})$ worst-case update time processing arbitrary $s,t$-distance queries in $\tilde{O}(n^{4/5})$ time. This constitutes the first non-trivial update/query tradeoff for this problem in the regime of sparse weighted directed graphs.
BibTeX
@inproceedings{karczmarz2023fully,
author = {Adam Karczmarz and Piotr Sankowski},
title = {{Fully Dynamic Shortest Paths in Sparse Digraphs}},
booktitle = {ICALP},
year = {2023},
url = {https://openreview.net/forum?id=bWKEKRkop3},
}