Almost-Optimal Sublinear Additive Spanners
- 2 December 2024
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- p. STOC23-215
Abstract
No abstract availableFunding Information
- European Research Council (803118 UncertainENV)
- Simons Foundation (820931)
This publication has 12 references indexed in Scilit:
- Lower Bounds on Sparse Spanners, Emulators, and Diameter-Reducing ShortcutsSIAM Journal on Discrete Mathematics, 2021
- Thorup–Zwick emulators are universally optimal hopsetsInformation Processing Letters, 2019
- A Hierarchy of Lower Bounds for Sublinear Additive SpannersSIAM Journal on Computing, 2018
- New Pairwise SpannersTheory of Computing Systems, 2016
- Additive spanners and (α, β)-spannersACM Transactions on Algorithms, 2010
- A simple and linear time randomized algorithm for computing sparse spanners in weighted graphsRandom Structures & Algorithms, 2006
- Sparse Sourcewise and Pairwise Distance PreserversSIAM Journal on Discrete Mathematics, 2006
- $(1 + \epsilon,\beta)$-Spanner Constructions for General GraphsSIAM Journal on Computing, 2004
- Fast Estimation of Diameter and Shortest Paths (Without Matrix Multiplication)SIAM Journal on Computing, 1999
- On sparse spanners of weighted graphsDiscrete & Computational Geometry, 1993