2026-07-21T20:24:35Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:11186 2024-03-06T10:47:39Z ddc:004 open_access

Reliable Hubs for Partially-Dynamic All-Pairs Shortest Paths in Directed Graphs Karczmarz, Adam Łącki, Jakub shortest paths dynamic incremental decremental directed graphs hubs We give new partially-dynamic algorithms for the all-pairs shortest paths problem in weighted directed graphs. Most importantly, we give a new deterministic incremental algorithm for the problem that handles updates in O~(mn^(4/3) log{W}/epsilon) total time (where the edge weights are from [1,W]) and explicitly maintains a (1+epsilon)-approximate distance matrix. For a fixed epsilon>0, this is the first deterministic partially dynamic algorithm for all-pairs shortest paths in directed graphs, whose update time is o(n^2) regardless of the number of edges. Furthermore, we also show how to improve the state-of-the-art partially dynamic randomized algorithms for all-pairs shortest paths [Baswana et al. STOC’02, Bernstein STOC’13] from Monte Carlo randomized to Las Vegas randomized without increasing the running time bounds (with respect to the O~(*) notation). Our results are obtained by giving new algorithms for the problem of dynamically maintaining hubs, that is a set of O~(n/d) vertices which hit a shortest path between each pair of vertices, provided it has hop-length Omega(d). We give new subquadratic deterministic and Las Vegas algorithms for maintenance of hubs under either edge insertions or deletions. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Adam Karczmarz and Jakub Łącki 2019 Is Part Of LIPIcs, Volume 144, 27th Annual European Symposium on Algorithms (ESA 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2019.65 urn:nbn:de:0030-drops-111862 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2019.65 eng https://creativecommons.org/licenses/by/3.0/legalcode