Faster spectral sparsification and numerical algorithms for SDD matrices

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.

Approximating s s - t t minimum cuts in O ⁡ ( n 2 ) {O}(n^{2}) time

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

Earlier work this paper cites.

Linear time deterministic algorithm for computing spanners for unweighted graphs

Eran Halperin and Uri Zwick · 1996

Earlier work this paper cites.

Better random sampling algorithms for flows in undirected graphs

David R. Karger · 1998

Earlier work this paper cites.

Database-friendly random projections

Dimitris Achlioptas · 2001

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

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.

Random walks and local cuts in graphs

Fan Chung · 2007

Cited alongside, same era.

Combinatorial and algebraic tools for optimal multilevel algorithms

Ioannis Koutis · 2007

Cited alongside, same era.

Graph sparsification by effective resistances

Daniel A. Spielman and Nikhil Srivastava · 2008

Cited alongside, same era.

A note on preconditioning by low-stretch spanning trees

Original

Approaching optimality for solving SDD systems

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

Later among the works it cites.

A general framework for graph sparsification

Wai Shing Fung, Ramesh Hariharan, Nicholas J. A. Harvey, and Debmalya Panigrahi · 2011

Later among the works it cites.

A nearly- m ​ log ⁡ n m\log n solver for SDD linear systems

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

Later among the works it cites.

Using petal-decompositions to build a low stretch spanning tree

Ittai Abraham and Ofer Neiman · 2012

Closest in time.

Improved spectral sparsification and numerical algorithms for sdd matrices

Ioannis Koutis, Alex Levin, and Richard Peng · 2012

Closest in time.

Spectral sparsification in the semi-streaming setting

JonathanA. Kelner and Alex Levin · 2013

Closest in time.