Lower Bounds on Sparse Spanners, Emulators, and Diameter-Reducing Shortcuts
Authors:
- Shang-En HuangSHShang-En Huang
- Seth PettieSPSeth Pettie
- 1 January 2021
- journal article
- research article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Discrete Mathematics
- Vol. 35 (3) , 2129-2144
Abstract
We prove better lower bounds on additive spanners and emulators, which are lossy compression schemes for undirected graphs, as well as lower bounds on shortcut sets, which reduce the diameter of di...Keywords
All Related Versions
Funding Information
- National Science Foundation (CCF-1514383, CCF-1637546, CCF-1815316)
This publication has 19 references indexed in Scilit:
- Additive spanners and (α, β)-spannersACM Transactions on Algorithms, 2010
- Low distortion spannersACM Transactions on Algorithms, 2009
- Sparse Sourcewise and Pairwise Distance PreserversSIAM Journal on Discrete Mathematics, 2006
- $(1 + \epsilon,\beta)$-Spanner Constructions for General GraphsSIAM Journal on Computing, 2004
- Testing subgraphs in large graphsRandom Structures & Algorithms, 2002
- All-Pairs Almost Shortest PathsSIAM Journal on Computing, 2000
- Fast Estimation of Diameter and Shortest Paths (Without Matrix Multiplication)SIAM Journal on Computing, 1999
- The convex hull of the integer points in a large ballMathematische Annalen, 1998
- Shortcutting Planar DigraphsCombinatorics, Probability and Computing, 1995
- On Sets of Integers Which Contain No Three Terms in Arithmetical ProgressionProceedings of the National Academy of Sciences, 1946