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...
| Publicado en: | Communications of the ACM Vol. 56; no. 8; pp. 87 - 95 |
|---|---|
| Autores principales: | , , , |
| Formato: | Artículo |
| Publicado: |
Association for Computing Machinery
Aug2013
|
| Materias: | |
| Acceso en línea: | Ver este registro en EBSCOhost |
| Sumario: | 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. |
|---|