A simple dynamic spanner via APSP

DOI10.4230/LIPICS.ICALP.2025.111MaRDI QIDQ7363199zbMATH OpenFDO

Authors Rasmus Kyng, Simon Meierhans, Gernot Zöcklein

Publication date 29 September 2026

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.ICALP.2025.111

Mathematics Subject Classification ID

Theory of software (68Nxx) Theory of computing (68Qxx)

Cites work

• A deterministic almost-linear time algorithm for minimum-cost flow
• A new deterministic algorithm for fully dynamic all-pairs shortest paths
• Dynamic low-stretch trees via dynamic low-diameter decompositions
• Fully dynamic algorithms for graph spanners via low-diameter router decomposition
• Fully dynamic randomized algorithms for graph spanners
• Fully-dynamic graph sparsifiers against an adaptive adversary
• Maximum flow and minimum-cost flow in almost-linear time
• On sparse spanners of weighted graphs
• Simple dynamic spanners with near-optimal recourse against an adaptive adversary

This page was built for publication: A simple dynamic spanner via APSP

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7363199)