2026-07-24T01:45:31Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:18136 2024-03-06T11:01:07Z ddc:004 open_access

Fully Dynamic Shortest Paths and Reachability in Sparse Digraphs Karczmarz, Adam Sankowski, Piotr dynamic shortest paths dynamic reachability dynamic transitive closure 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]. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Adam Karczmarz and Piotr Sankowski 2023 Is Part Of LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2023.84 urn:nbn:de:0030-drops-181363 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.84 eng https://creativecommons.org/licenses/by/4.0/legalcode