Constant Arboricity Spectral Sparsifiers.
2018
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.
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
3
References
0
Citations
NaN
KQI