Constant Arboricity Spectral Sparsifiers
classification
💻 cs.DS
keywords
constantforestssparsifiersunionarboricityboundariesestimateevery
read the original abstract
We show that every graph is spectrally similar to the union of a constant number of forests. Moreover, we show that Spielman-Srivastava sparsifiers are the union of O(logn) forests. This result can be used to estimate boundaries of small subsets of vertices in nearly optimal query time.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.