Cover Image
QR Code

Spectral Sparsification of Graphs: Theory and Algorithms.

The article discusses graph sparsification as an approximation of arbitrary graphs by sparse graphs, focusing on the potential implementation of graph sparsification in designing nearly linear-time algorithms for solving some linear equation systems with diagonally dominant matrices and finding maxi...

Full description

Published in:Communications of the ACM Vol. 56; no. 8; pp. 87 - 95
Main Authors: Batson, Joshua, Spielman, Daniel A., Teng, Shang-Hua, Srivastava, Nikhil
Format: Article
Published: Association for Computing Machinery Aug2013
Subjects:
Graph theory
Sparse graphs
Algorithm research
Network analysis (Planning)
Laplacian matrices
Linear equations
Online Access:View this record in EBSCOhost
Summary:The article discusses graph sparsification as an approximation of arbitrary graphs by sparse graphs, focusing on the potential implementation of graph sparsification in designing nearly linear-time algorithms for solving some linear equation systems with diagonally dominant matrices and finding maximum flows and minimum cuts for undirected networks. Topics include similarities such as cut similarities and spectral similarities, sampling by effective resistance, Laplacian systems, and fast sparsification algorithms.