Fully Dynamic Algorithms for Graph Spanners via Low-Diameter Router Decomposition Preliminary version appeared in SODA 2025

Julia Chuzhoy, Merav Parter · 2026

Read Fully Dynamic Algorithms for Graph Spanners via Low-Diameter Router Decomposition Preliminary version appeared in SODA 2025 by Julia Chuzhoy, Merav Parter (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2601-20718.txt.

Description

Julia Chuzhoy and Merav Parter keep sparse network stand-ins up to date while the network itself keeps changing. Their 2026 paper studies fully dynamic algorithms for graph spanners. A spanner is a sparse subgraph that preserves distances between all vertex pairs. The distances may stretch by a factor called t, the stretch. Sparsity is the point: far fewer edges than the full graph. Roads, networks, and data all use such stand-ins.

Fully dynamic means edges arrive and vanish over time. The algorithm must repair the spanner after each change, fast. Their route uses low-diameter router decomposition. The graph is broken into clusters that act as routers. A preliminary version appeared at SODA 2025. The work serves any system whose map changes while it is being used.

Catalog record

CREATORJulia Chuzhoy, Merav Parter
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE466 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2601-20718

Browse the full library · About the Tower of Babel