2026-07-24T01:44:57Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:23488 2025-10-02T12:56:37Z ddc:004 open_access

A Simple Dynamic Spanner via APSP Kyng, Rasmus Meierhans, Simon Zöcklein, Gernot Dynamic graph algorithms Spanner Dynamic Greedy Spanner We give a simple algorithm for maintaining a n^{o(1)}-approximate spanner H of a graph G with n vertices as G receives edge updates by reduction to the dynamic All-Pairs Shortest Paths (APSP) problem. Given an initially empty graph G, our algorithm processes m insertions and n deletions in total time m^{1 + o(1)} and maintains an initially empty spanner H with total recourse n^{1 + o(1)}. When the number of insertions is much larger than the number of deletions, this notably yields recourse sub-linear in the total number of updates. Our simple algorithm can be extended to maintain a δ ≥ ω(1)-approximate spanner with n^{1+o(1)} edges throughout a sequence of m insertions and D deletions with amortized update time n^{o(1)} and total recourse n^{1 + o(1)} + n^{o(1)} ⋅ D via batching. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Rasmus Kyng and Simon Meierhans and Gernot Zöcklein 2025 Is Part Of LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2025.111 urn:nbn:de:0030-drops-234886 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.111 eng https://creativecommons.org/licenses/by/4.0/legalcode