Fetching the paper…
Reading the bibliography…
We describe a simple algorithm for spectral graph sparsification, based on iterative computations of weighted spanners and uniform sampling.
Multigrid Methods
James H. Bramble · 1993
Earlier work this paper cites.
Random walks and electric networks, 2000
Peter G. Doyle and J. Laurie Snell · 2000
Earlier work this paper cites.
Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems
Daniel A. Spielman and Shang-Hua Teng · 2004
Earlier work this paper cites.
Approximate distance oracles
Mikkel Thorup and Uri Zwick · 2005
Earlier work this paper cites.
A simple and linear time randomized algorithm for computing sparse spanners in weighted graphs
Surender Baswana and Sandeep Sen · 2007
Earlier work this paper cites.
Graph partitioning into isolated, high conductance clusters: Theory, computation and applications to preconditioning
Ioannis Koutis and Gary L. Miller · 2008
Earlier work this paper cites.
Graph sparsification by effective resistances
Daniel A. Spielman and Nikhil Srivastava · 2008
Earlier work this paper cites.
Twice-Ramanujan sparsifiers
Joshua D. Batson, Daniel A. Spielman, and Nikhil Srivastava · 2009
Earlier work this paper cites.
The combinatorial multigrid solver
Ioannis Koutis and Gary Miller · 2009
Earlier work this paper cites.
Subgraph sparsification and nearly optimal ultrasparsifiers
Alexandra Kolla, Yury Makarychev, Amin Saberi, and Shang-Hua Teng · 2010
Cited alongside, same era.
Approaching optimality for solving SDD systems
Ioannis Koutis, Gary L. Miller, and Richard Peng · 2010
Cited alongside, same era.
The laplacian paradigm: emerging algorithms for massive graphs
Shang-Hua Teng · 2010
Cited alongside, same era.
Spectral sparsification in the semi-streaming setting
Jonathan A. Kelner and Alex Levin · 2011
Cited alongside, same era.
A nearly m log n m\log n solver for SDD linear systems
Ioannis Koutis, Gary L. Miller, and Richard Peng · 2011
Cited alongside, same era.
Towards an SDP-based approach to spectral methods: A nearly-linear-time algorithm for graph partitioning and decomposition
Lorenzo Orecchia and Nisheeth K. Vishnoi · 2011
Improved spectral sparsification and numerical algorithms for SDD matrices
Ioannis Koutis, Alex Levin, and Richard Peng · 2012
Later among the works it cites.
A fast solver for a class of linear systems
Ioannis Koutis, Gary L. Miller, and Richard Peng · 2012
Later among the works it cites.
Lean Algebraic Multigrid (LAMG): Fast Graph Laplacian Linear Solver
Oren E. Livne and Achi Brandt · 2012
Later among the works it cites.
User-friendly tail bounds for sums of random matrices
Joel A Tropp · 2012
Later among the works it cites.
Spectral sparsification of graphs: theory and algorithms
Joshua D. Batson, Daniel A. Spielman, Nikhil Srivastava, and Shang-Hua Teng · 2013
Later among the works it cites.
A Simple, Combinatorial Algorithm for Solving SDD Systems in Nearly-Linear Time
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Cited alongside, same era.
Matrix Concentration
N. Harvey · 2012
Cited alongside, same era.
Spectral sparsification via random spanners
Michael Kapralov and Rina Panigrahy · 2012
Cited alongside, same era.
Faster spectral sparsification and numerical algorithms for sdd matrices
Ioannis Koutis, Alex Levin, and Richard Peng · 2012
Cited alongside, same era.
Jonathan A. Kelner, Lorenzo Orecchia, Aaron Sidford, and Zeyuan Allen Zhu · 2013
Later among the works it cites.
Efficient preconditioning of laplacian matrices for computer graphics
Dilip Krishnan, Raanan Fattal, and Richard Szeliski · 2013
Later among the works it cites.
Algorithm design using spectral graph theory
Richard Peng · 2013
Later among the works it cites.
An efficient parallel solver for SDD linear systems
Richard Peng and Daniel A. Spielman · 2013
Later among the works it cites.