Constructing Linear-Sized Spectral Sparsification in Almost-Linear Time

Yin Tat Lee, He Sun

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

We present the first almost-linear time algorithm for constructing linear-sized spectral sparsification for graphs. This improves all previous constructions of linear-sized spectral sparsification, which requires Ω(n2) time [1], [2], [3]. A key ingredient in our algorithm is a novel combination of two techniques used in literature for constructing spectral sparsification: Random sampling by effective resistance [4], and adaptive constructions based on barrier functions [1], [3].
Original languageEnglish
Title of host publicationIEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015, Berkeley, CA, USA, 17-20 October, 2015
Pages250-269
Number of pages20
ISBN (Electronic)978-1-4673-8191-8
DOIs
Publication statusPublished - 2015
EventFoundations of Computer Science 2015 - California, Berkley, United States
Duration: 17 Oct 201520 Oct 2015
http://ieee-focs.org/

Conference

ConferenceFoundations of Computer Science 2015
Country/TerritoryUnited States
CityBerkley
Period17/10/1520/10/15
Internet address

Fingerprint

Dive into the research topics of 'Constructing Linear-Sized Spectral Sparsification in Almost-Linear Time'. Together they form a unique fingerprint.

Cite this