@article{ca34f964422d41f6883eb505f4d58de4,
title = "Simple parallel and distributed algorithms for spectral graph sparsification",
abstract = "We describe simple algorithms for spectral graph sparsification, based on iterative computations of weighted spanners and sampling. Leveraging the algorithms of Baswana and Sen for computing spanners, we obtain the first distributed spectral sparsification algorithm in the CONGEST model.We also obtain a parallel algorithm with improved work and time guarantees, as well as other natural distributed implementations. Combining this algorithm with the parallel framework of Peng and Spielman for solving symmetric diagonally dominant linear systems, we get a parallel solver that is significantlymore efficient in terms of the total work.",
keywords = "SDD linear systems, Sparsest cut, Spectral sparsification",
author = "Ioannis Koutis and Xu, {Shen Chen}",
note = "Funding Information: This work was supported by NSF CAREER award CCF-1149048. Part of this work was done while the author was visiting the Institute of Computational and Experimental Mathematics (ICERM) in Spring 2014. Authors{\textquoteright} addresses: I. Koutis, Department of Computer Science, College of Natural Sciences, University of Puerto Rico, Rio Piedras Campus, PO Box 70377, San Juan, PR 00936–8377; email: ioannis.koutis@upr.edu; S. C. Xu, Computer Science Department, Carnegie Mellon University, 5000 Forbes Ave, Pittsburgh, PA 15213; email: shenchex@cs.cmu.edu. Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies show this notice on the first page or initial screen of a display along with the full citation. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, to republish, to post on servers, to redistribute to lists, or to use any component of this work in other works requires prior specific permission and/or a fee. Permissions may be requested from Publications Dept., ACM, Inc., 2 Penn Plaza, Suite 701, New York, NY 10121-0701 USA, fax +1 (212) 869-0481, or permissions@acm.org. {\textcopyright}c 2016 ACM 2329-4949/2016/08-ART14 $15.00 DOI: http://dx.doi.org/10.1145/2948062",
year = "2016",
month = aug,
doi = "10.1145/2948062",
language = "English (US)",
volume = "3",
journal = "ACM Transactions on Parallel Computing",
issn = "2329-4949",
publisher = "Association for Computing Machinery (ACM)",
number = "2",
}