Greedy Completion for Weighted $(α,β)$-Spanners
This addresses a gap in graph spanner theory for weighted graphs, providing a new spanner construction that was previously unknown, though it appears incremental as it builds on existing methods.
The paper tackles the problem of constructing $(\\alpha,\eta)$-spanners for weighted graphs by proposing a greedy completion procedure that generalizes prior work, resulting in the first construction of $(k,k-1)$-spanners with size $\tilde{O}(n^{1+1/k})$ for such graphs.
We study $(α,β)$-spanners for weighted graphs. We propose a simple greedy completion procedure which starts from a sparse initial graph, and repeatedly fixes pairs of vertices with a bad stretch, generalizing Kunedsen's additive completion [SWAT '14]. As an application, we construct $(k,k-1)$-spanners for weighted graphs of size $\tilde{O}(n^{1+1/k})$, which were previously unknown.