Fully Dynamic Shortest Paths and Reachability in Sparse Digraphs

Autor: Karczmarz, Adam, Sankowski, Piotr
Jazyk: angličtina
Rok vydání: 2023
Předmět:
DOI: 10.4230/lipics.icalp.2023.84
Popis: We study the exact fully dynamic shortest paths problem. For real-weighted directed graphs, we show a deterministic fully dynamic data structure with Õ(mn^{4/5}) worst-case update time processing arbitrary s,t-distance queries in Õ(n^{4/5}) time. This constitutes the first non-trivial update/query tradeoff for this problem in the regime of sparse weighted directed graphs. Moreover, we give a Monte Carlo randomized fully dynamic reachability data structure processing single-edge updates in Õ(n√m) worst-case time and queries in O(√m) time. For sparse digraphs, such a tradeoff has only been previously described with amortized update time [Roditty and Zwick, SIAM J. Comp. 2008].
LIPIcs, Vol. 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023), pages 84:1-84:20
Databáze: OpenAIRE