Approaching optimality for solving SDD systems

Ioannis Koutis, Gary L. Miller, Richard Peng

We present an algorithm that on input of an $n$-vertex $m$-edge weighted graph $G$ and a value $k$, produces an {\em incremental sparsifier} $\hat{G}$ with $n-1+m/k$ edges, such…