Spectral Sparsification of Graphs: Theory and Algorithms

被引:120
作者
Batson, Joshua [1 ]
Spielman, Daniel A. [2 ]
Srivastava, Nikhil [3 ]
Teng, Shang-Hua
机构
[1] MIT, Cambridge, MA 02139 USA
[2] Yale Univ, New Haven, CT 06520 USA
[3] Microsoft Res, Bangalore, Karnataka, India
基金
美国国家科学基金会;
关键词
36;
D O I
10.1145/2492007.2492029
中图分类号
TP3 [计算技术、计算机技术];
学科分类号
0812 ;
摘要
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.
引用
收藏
页码:87 / 94
页数:8
相关论文
共 33 条
[1]  
ABRAHAM I, 2012, USING PETAL DECOMPOS
[2]   ON SPARSE SPANNERS OF WEIGHTED GRAPHS [J].
ALTHOFER, I ;
DAS, G ;
DOBKIN, D ;
JOSEPH, D ;
SOARES, J .
DISCRETE & COMPUTATIONAL GEOMETRY, 1993, 9 (01) :81-100
[3]  
ANDERSEN R, 2009, FINDING SPARSE CUTS, P235
[4]  
Andersen R, 2006, ANN IEEE SYMP FOUND, P475
[5]  
[Anonymous], 1970, Problems in Analysis
[6]  
[Anonymous], 2005, P 22 INT C MACHINE L
[7]  
BATSON JD, 2012, TWICE RAMANUJAN SPAR, V6, P1704
[8]  
Benczur A. A., 1996, Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, P47, DOI 10.1145/237814.237827
[9]  
BOLLOBAS B, 1988, ISOPERIMETRIC NUMBER, P241
[10]  
CHANDRA AK, 1989, ELECT RESISTANCE GRP, P574