A nearly-mlogn time solver for SDD linear systems

Algebraic connectivity of graphs

Miroslav Fiedler · 1973

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.

Fibonacci heaps and their uses in improved network optimization algorithms

Michael L. Fredman and Robert Endre Tarjan · 1987

Earlier work this paper cites.

Approximating s-t

András A. Benczúr and David R. Karger · 1996

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.

Random walks and electric networks, 2000

Peter G. Doyle and J. Laurie Snell · 2000

Earlier work this paper cites.

Support theory for preconditioning

Erik G. Boman and Bruce Hendrickson · 2003

Earlier work this paper cites.

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.

Lower-stretch spanning trees

Michael Elkin, Yuval Emek, Daniel A. Spielman, and Shang-Hua Teng · 2005

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.

Nearly tight low stretch spanning trees

Ittai Abraham, Yair Bartal, and Ofer Neiman · 2008

Subgraph sparsification and nearly optimal ultrasparsifiers

Original

Alexandra Kolla, Yury Makarychev, Amin Saberi, and Shang-Hua 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.

Approaching optimality for solving SDD systems

Original

Ioannis Koutis, Gary L. Miller, and Richard Peng · 2010

Later among the works it cites.

Approaching optimality for solving SDD systems

Ioannis Koutis, Gary L. Miller, and Richard Peng · 2010

Later among the works it cites.

A faster algorithm for the single source shortest path problem with few distinct positive lengths

James B. Orlin, Kamesh Madduri, K. Subramani, and M. Williamson · 2010

Later among the works it cites.