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 |
| fields | @attributes: recordID: 1 pdfLink: plink: https://search.ebscohost.com/login.aspx?direct=true&db=hlh&AN=89595608&site=ehost-live header: @attributes: shortDbName: hlh uiTerm: 89595608 longDbName: Humanities International Complete uiTag: AN controlInfo: bkinfo: jinfo: jid: 00010782 ACM jtl: Communications of the ACM issn: 00010782 maglogo: N pubinfo: dt: Aug2013 vid: 56 iid: 8 pid: 68 pub: Association for Computing Machinery artinfo: ui: 89595608 10.1145/2492007.2492029 ppf: 87 ppct: 8 formats: tig: atl: Spectral Sparsification of Graphs: Theory and Algorithms. aug: au: Batson, Joshua Spielman, Daniel A. Teng, Shang-Hua Srivastava, Nikhil affil: Mathematics, MIT Computer Science & Applied Mathematics, Yale University. Computer Science, USC Microsoft Research, Bangalore su: Graph theory Sparse graphs Algorithm research Network analysis (Planning) Laplacian matrices Linear equations sug: subj: Graph theory Sparse graphs Algorithm research Network analysis (Planning) Laplacian matrices Linear equations ab: 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. pubtype: Periodical doctype: Article src: R language: English refInfo: copyright: @attributes: flag: Y dt: @attributes: year: 2013 holdings: @attributes: islocal: N |
|---|