Constructing Linear-Sized Spectral Sparsification in Almost-Linear Time

He Sun, Yin Tat Lee

Research output: Chapter in Book/Report/Conference proceedingConference Contribution (Conference Proceeding)

24 Citations (Scopus)

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 Ω(n 2 ) 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 publication2015 IEEE 56th Annual Symposium on Foundations of Computer Science
PublisherInstitute of Electrical and Electronics Engineers (IEEE)
Pages250-269
Number of pages20
ISBN (Electronic)9781467381918
DOIs
Publication statusPublished - 17 Oct 2015

Publication series

Name
ISSN (Print)0272-5428

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

Cite this