Constant Arboricity Spectral Sparsifiers

08/16/2018
by   Timothy Chu, et al.
0

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.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset