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+ε)(2k1)-spanner of lightness Oε(n1/k), and recent followup work by Le and Solomon [STOC '23] generalized the proof strategy and improved the dependence on ε. We give a new proof of this result, with the improved ε-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 123 times.
    This article's PDF has been downloaded 74 times.