Communications of the ACM
Research Archive
The Research archive provides access to all Research articles published in past issues of Communications of the ACM.
August 2013
From Communications of the ACM
Technical Perspective: Every Graph Is Essentially Sparse
The following paper by Batson, Spielman, Srivastava, and Teng surveys one of the most important recent intellectual achievements of theoretical computer science, demonstrating that every weighted graph is close to a sparse…
From Communications of the ACM
Spectral Sparsification of Graphs: Theory and Algorithms
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…