The 4/3 Additive Spanner Exponent Is Tight

DOI10.1145/3088511zbMath1410.68263arXiv1511.00700OpenAlexW2750647157MaRDI QIDQ4640279

Amir Abboud, Greg Bodwin

Publication date: 17 May 2018

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1511.00700

zbMATH Keywords

graph theorylower boundsshortest pathsspannersgraph sketching

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Distance in graphs (05C12) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (17)

A Hierarchy of Lower Bounds for Sublinear Additive Spanners ⋮ Lossless Prioritized Embeddings ⋮ On additive spanners in weighted graphs with local error ⋮ Improved weighted additive spanners ⋮ Reachability Preservers: New Extremal Bounds and Approximation Algorithms ⋮ Multi-priority graph sparsification ⋮ The sparsest additive spanner via multiple weighted BFS trees ⋮ Unnamed Item ⋮ Lower Bounds on Sparse Spanners, Emulators, and Diameter-Reducing Shortcuts ⋮ Graph spanners: a tutorial review ⋮ NP-hardness and fixed-parameter tractability of the minimum spanner problem ⋮ Unnamed Item ⋮ Sparsification lower bound for linear spanners in directed graphs ⋮ The Sparsest Additive Spanner via Multiple Weighted BFS Trees ⋮ Bounded degree spanners of the hypercube ⋮ Toward Tight Approximation Bounds for Graph Diameter and Eccentricities ⋮ New Results on Linear Size Distance Preservers

This page was built for publication: The 4/3 Additive Spanner Exponent Is Tight