Spectral sparsification of graphs
Open Access
- 1 August 2013
- journal article
- Published by Association for Computing Machinery (ACM) in Communications of the ACM
- Vol. 56 (8) , 87-94
Abstract
Graph sparsification is the approximation of an arbitrary graph by a sparse graph. We explain what it means for one graph to be a spectral approximation of another and review the development of algorithms for spectral sparsification. In addition to being an interesting concept, spectral sparsification has been an important tool in the design of nearly linear-time algorithms for solving systems of linear equations in symmetric, diagonally dominant matrices. The fast solution of these linear systems has already led to breakthrough results in combinatorial optimization, including a faster algorithm for finding approximate maximum flows and minimum cuts in an undirected network.Keywords
This publication has 15 references indexed in Scilit:
- Spectral sparsification via random spanners2012
- A Nearly-m log n Time Solver for SDD Linear Systems2011
- Electrical flows, laplacian systems, and faster approximation of maximum flow in undirected graphs2011
- Spectral Sparsification of GraphsSIAM Journal on Computing, 2011
- Graph Sparsification by Effective ResistancesSIAM Journal on Computing, 2011
- Subgraph sparsification and nearly optimal ultrasparsifiers2010
- Approximating s-t minimum cuts in Õ(n2) time1996
- An Optimal Synchronizer for the HypercubeSIAM Journal on Computing, 1989
- Approximate counting, uniform generation and rapidly mixing Markov chainsInformation and Computation, 1989
- The electrical resistance of a graph captures its commute and cover times1989