Bootstrapping dynamic apsp via sparsification

DOI10.4230/LIPICS.ESA.2025.113MaRDI QIDQ7322531zbMATH OpenFDO

Authors Rasmus Kyng, Simon Meierhans, Gernot Zöcklein

Publication date 31 August 2026

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.ESA.2025.113

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Cites work

• A deterministic almost-linear time algorithm for minimum-cost flow
• A new deterministic algorithm for fully dynamic all-pairs shortest paths
• Approximate distance oracles
• Bootstrapping dynamic distance oracles
• Decremental all-pairs shortest paths in deterministic near-linear time
• Decremental Single-Source Shortest Paths on Undirected Graphs in Near-Linear Total Update Time
• Deterministic decremental SSSP and approximate min-cost flow in almost-linear time
• Deterministic incremental APSP with polylogarithmic update time and stretch
• scientific article; zbMATH DE number 7788413 (Why is no real title available?)
• scientific article; zbMATH DE number 7788485 (Why is no real title available?)
• Maximum flow and minimum-cost flow in almost-linear time
• Near-optimal approximate decremental all pairs shortest paths
• On sparse spanners of weighted graphs
• Simple dynamic spanners with near-optimal recourse against an adaptive adversary

This page was built for publication: Bootstrapping dynamic apsp via sparsification

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