72 citations · 174 across the 24 of their papers we have counts for
Showing 2008Show all
2 papers · 1 filter
cs.DS2008★ 6 cited
Twice-Ramanujan Sparsifiers
Joshua Batson, Daniel A. Spielman, Nikhil Srivastava
We prove that every graph has a spectral sparsifier with a number of edges linear in its number of vertices. As linear-sized spectral sparsifiers of complete graphs are expanders,…
cs.DS2008★ 7 cited
Graph Sparsification by Effective Resistances
Daniel A. Spielman, Nikhil Srivastava
We present a nearly-linear time algorithm that produces high-quality sparsifiers of weighted graphs. Given as input a weighted graph and a parameter , we produce a…