Faster spectral sparsification and numerical algorithms for SDD matrices

Ioannis Koutis, Alex Levin, Richard Peng

We study algorithms for spectral graph sparsification. The input is a graph $G$ with $n$ vertices and $m$ edges, and the output is a sparse graph $\tilde{G}$ that approximates $G$…