Fetching the paper…
Reading the bibliography…
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 that the condition number of $G$ with $\hat{G}$ is bounded above by $\tilde{O}(k\log^2 n)$, with probability $1-p$.
Algebraic connectivity of graphs
Miroslav Fiedler · 1973
Earlier work this paper cites.
Nested dissection of a regular finite element mesh
Alan George · 1973
Earlier work this paper cites.
Generalized nested dissection
R.J. Lipton, D. Rose, and R.E. Tarjan · 1979
Earlier work this paper cites.
Applications of path compression on balanced trees
Robert Endre Tarjan · 1979
Earlier work this paper cites.
A linear-time algorithm for a special case of disjoint set union
Harold N. Gabow and Robert Endre Tarjan · 1983
Earlier work this paper cites.
Solving linear equations with symmetric diagonally dominant matrices by constructing good preconditioners
P.M. Vaidya · 1991
Earlier work this paper cites.
Iterative Solution Methods
Owe Axelsson · 1994
Earlier work this paper cites.
A graph-theoretic game and its application to the
Noga Alon, Richard Karp, David Peleg, and Douglas West · 1995
Earlier work this paper cites.
Performance evaluation of a parallel preconditioner
K.D. Gremban, Gary L. Miller, and M. Zagha · 1995
Earlier work this paper cites.
Combinatorial Preconditioners for Sparse, Symmetric, Diagonally Dominant Linear Systems
Keith Gremban · 1996
Earlier work this paper cites.
Spectral partitioning works: Planar graphs and finite element meshes
Daniel A. Spielman and Shang-Hua Teng · 1996
Earlier work this paper cites.
Spectral Graph Theory
F.R.K. Chung · 1997
Earlier work this paper cites.
Topics in Optimization and Sparse Linear Systems
Anil Joshi · 1997
Earlier work this paper cites.
Algebraic Graph Theory
Gordon Royle and Chris Godsil · 1997
Cited alongside, same era.
Random walks and electric networks, 2000
Peter G. Doyle and J. Laurie Snell · 2000
Cited alongside, same era.
Support theory for preconditioning
Erik G. Boman and Bruce Hendrickson · 2003
Cited alongside, same era.
Solving Sparse, Symmetric, Diagonally-Dominant Linear Systems in Time 0(
Daniel A. Spielman and Shang-Hua Teng · 2003
Cited alongside, same era.
Solving elliptic finite element systems in near-linear time with support preconditioners
Erik G. Boman, Bruce Hendrickson, and Stephen A. Vavasis · 2004
Cited alongside, same era.
Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems
Daniel A. Spielman and Shang-Hua Teng · 2004
Cited alongside, same era.
Graph partitioning into isolated, high conductance clusters: Theory, computation and applications to preconditioning
Ioannis Koutis and Gary L. Miller · 2008
Later among the works it cites.
Real-time gradient-domain painting
James McCann and Nancy S. Pollard · 2008
Later among the works it cites.
Faster approximate lossy generalized flow via interior point algorithms
Daniel A. Spielman and Samuel I. Daitch · 2008
Later among the works it cites.
Graph sparsification by effective resistances, 2008
Daniel A. Spielman and Nikhil Srivastava · 2008
Later among the works it cites.
Twice-Ramanujan sparsifiers
Joshua D. Batson, Daniel A. Spielman, and Nikhil Srivastava · 2009
Later among the works it cites.
Faster generation of random spanning trees
Jonathan A. Kelner and Aleksander Madry · 2009
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Support-graph preconditioners
Marshall Bern, John R. Gilbert, Bruce Hendrickson, Nhat Nguyen, and Sivan Toledo · 2005
Cited alongside, same era.
Lower-stretch spanning trees
Michael Elkin, Yuval Emek, Daniel A. Spielman, and Shang-Hua Teng · 2005
Cited alongside, same era.
Local graph partitioning using pagerank vectors
Reid Andersen, Fan Chung, and Kevin Lang · 2006
Cited alongside, same era.
Nearly-linear time algorithms for preconditioning and solving symmetric, diagonally dominant linear systems
Daniel A. Spielman and Shang-Hua Teng · 2006
Cited alongside, same era.
Harmonic coordinates for character articulation
Pushkar Joshi, Mark Meyer, Tony DeRose, Brian Green, and Tom Sanocki · 2007
Cited alongside, same era.
Sampling from large matrices: An approach through geometric functional analysis
Mark Rudelson and Roman Vershynin · 2007
Cited alongside, same era.
Subgraph sparsification and nearly optimal ultrasparsifiers
Alexandra Kolla, Yury Makarychev, Amin Saberi, and Shanghua Teng · 2009
Later among the works it cites.
Combinatorial preconditioners and multilevel solvers for problems in computer vision and image processing
Ioannis Koutis, Gary L. Miller, Ali Sinop, and David Tolliver · 2009
Later among the works it cites.
Combinatorial preconditioners and multilevel solvers for problems in computer vision and image processing
Ioannis Koutis, Gary L. Miller, and David Tolliver · 2009
Later among the works it cites.
A general framework for graph sparsification
Ramesh Hariharan and Debmalya Panigrahi · 2010
Closest in time.
Algorithms, Graph Theory, and Linear Equations in Laplacian Matrices
Daniel A. Spielman · 2010
Closest in time.
The Laplacian Paradigm: Emerging Algorithms for Massive Graphs
Shang-Hua Teng · 2010
Closest in time.