• DocumentCode
    3710054
  • Title

    Constructing Linear-Sized Spectral Sparsification in Almost-Linear Time

  • Author

    Yin Tat Lee;He Sun

  • Author_Institution
    Dept. of Math., MIT, Cambridge, MA, USA
  • fYear
    2015
  • Firstpage
    250
  • Lastpage
    269
  • 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].
  • Keywords
    "Approximation methods","Approximation algorithms","Eigenvalues and eigenfunctions","Algorithm design and analysis","Laplace equations","Resistance","Computer science"
  • Publisher
    ieee
  • Conference_Titel
    Foundations of Computer Science (FOCS), 2015 IEEE 56th Annual Symposium on
  • ISSN
    0272-5428
  • Type

    conf

  • DOI
    10.1109/FOCS.2015.24
  • Filename
    7354398
    • Link To Document
    https://search.isc.ac/dl/search/defaultta.aspx?DTC=49&DC=3710054