Home → Magazine Archive → August 2013 (Vol. 56, No. 8) → Spectral Sparsification of Graphs: Theory and Algorithms → Abstract

Spectral Sparsification of Graphs: Theory and Algorithms

By Joshua Batson, Daniel A. Spielman, Nikhil Srivastava, Shang-Hua Teng

Communications of the ACM, Vol. 56 No. 8, Pages 87-94

[article image]

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.

The full text of this article is premium content


No entries found