\((\alpha, \beta)\)-Spanners and Hybrid Spanners with Nearly Tight Bounds
Abstract
An \((\alpha,\beta)\)-spanner of an \(n\)-vertex undirected, unweighted graph \(G=(V,E)\) is a subgraph \(H\) satisfying, for all \(u,v\in V\), \(\mathrm{dist}_H(u,v)\le \alpha\cdot \mathrm{dist}_G(u,v)+\beta\). For any \(k\in\mathbb{N}\), classical results show that a \((2k-1,0)\)-spanner with \(O(n^{1+1/k})\) edges exists and is asymptotically optimal under Erdős’ girth conjecture. This conditional lower bound applies only to adjacent pairs, leaving open the possibility of improved stretch for more distant pairs.
Fields of Study & Subjects
Advanced Graph Theory Research
Limits and Structures in Graph Theory
Complexity and Algorithms in Graphs
Publication details
- Journal / source
- Society for Industrial and Applied Mathematics eBooks
- Pages
- 3511–3535
- Publication date
- 1 January 2026
- Language
- EN