Constructing Linear-Sized Spectral Sparsification in Almost-Linear Time
Constructing Linear-Sized Spectral Sparsification in Almost-Linear Time
We present the first almost-linear time algorithm for constructing linear-sized spectral sparsification for graphs. This improves all previous constructions of linear-sized spectral sparsification, which requires Ω(n <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup> ) time [1], [2], [3]. A key ingredient in our algorithm is a novel combination of two techniques used in literature …