Constructing Linear Sized Spectral Sparsification in Almost Linear Time
We present an almost linear time algorithm for constructing a spectral sparsifier with the number of edges linear in its number of vertices. This improves all previous constructions of linear sized.
SIAM J. Comput.