2026-08-17T10:35:24Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:4685 2024-03-06T10:35:13Z ddc:004 open_access

Fully Dynamic All-Pairs Shortest Paths: Breaking the O(n) Barrier Abraham, Ittai Chechik, Shiri Talwar, Kunal Shortest Paths Dynamic Algorithms A fully dynamic approximate distance oracle is a distance reporting data structure that supports dynamic insert edge and delete edge operations. In this paper we break a longstanding barrier in the design of fully dynamic all-pairs approximate distance oracles. All previous results for this model incurred an amortized cost of at least Omega(n) per operation. We present the first construction that provides constant stretch and o(m) amortized update time. For graphs that are not too dense (where |E| = O(|V|^{2-delta}) for some delta>0 we break the O(n) barrier and provide the first construction with constant stretch and o(n) amortized cost. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Ittai Abraham and Shiri Chechik and Kunal Talwar 2014 Is Part Of LIPIcs, Volume 28, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX-RANDOM.2014.1 urn:nbn:de:0030-drops-46857 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2014.1 eng https://creativecommons.org/licenses/by/3.0/legalcode