Greg Bodwin - An Alternate Proof of Near-Optimal Light Spanners

theoretics:13191 - TheoretiCS, January 10, 2025, Volume 4 - https://doi.org/10.46298/theoretics.25.2
An Alternate Proof of Near-Optimal Light SpannersArticle

Authors: Greg Bodwin ORCID

    In 2016, a breakthrough result of Chechik and Wulff-Nilsen [SODA '16] established that every $n$-node graph $G$ has a $(1+\varepsilon)(2k-1)$-spanner of lightness $O_{\varepsilon}(n^{1/k})$, and recent followup work by Le and Solomon [STOC '23] generalized the proof strategy and improved the dependence on $\varepsilon$. We give a new proof of this result, with the improved $\varepsilon$-dependence. Our proof is a direct analysis of the often-studied greedy spanner, and can be viewed as an extension of the folklore Moore bounds used to analyze spanner sparsity.


    Volume: Volume 4
    Published on: January 10, 2025
    Accepted on: November 24, 2024
    Submitted on: March 7, 2024
    Keywords: Computer Science - Data Structures and Algorithms,Computer Science - Discrete Mathematics,Mathematics - Combinatorics

    Consultation statistics

    This page has been seen 33 times.
    This article's PDF has been downloaded 26 times.