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