Fully Dynamic Shortest Paths in Sparse Digraphs
<|reference_start|>Fully Dynamic Shortest Paths in Sparse Digraphs: 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.<|reference_end|>
@article{karczmarz2024fully,
    title={Fully Dynamic Shortest Paths in Sparse Digraphs},
    author={Adam Karczmarz, Piotr Sankowski},
    journal={arXiv preprint arXiv:2408.14406},
    year={2024},
    doi={10.4230/LIPICS.ICALP.2023.84},
    archivePrefix={arXiv},
    eprint={2408.14406},
    primaryClass={cs.DS}
}