The 4/3 additive spanner exponent is tight

DOI10.1145/2897518.2897555zbMath1376.05094OpenAlexW2227069303MaRDI QIDQ5361843

Greg Bodwin, Amir Abboud

Publication date: 29 September 2017

Published in: Proceedings of the forty-eighth annual ACM symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/2897518.2897555

zbMATH Keywords

lower boundsshortest pathsspannersgraph sketching

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Distance in graphs (05C12) Graph representations (geometric and intersection representations, etc.) (05C62) Graph operations (line graphs, products, etc.) (05C76)

Related Items (12)

Source-wise round-trip spanners ⋮ Deterministic improved round-trip spanners ⋮ Efficient Oracles and Routing Schemes for Replacement Paths ⋮ Communication-efficient distributed graph clustering and sparsification under duplication models ⋮ New pairwise spanners ⋮ Distributed construction of purely additive spanners ⋮ A fast algorithm for source-wise round-trip spanners ⋮ Improved Guarantees for Vertex Sparsification in Planar Graphs ⋮ Approximate distance oracles with improved stretch for sparse graphs ⋮ Distance-Preserving Graph Contractions ⋮ Distance-Preserving Graph Contractions ⋮ Sparse Weight Tolerant Subgraph for Single Source Shortest Path

This page was built for publication: The 4/3 additive spanner exponent is tight