Random Spanning Trees for Expanders, Sparsifiers, and Virtual Network Security

Shlomi Dolev, Daniel Khankin

This work describes probabilistic methods for utilizing random spanning trees generated via a random walk process. Goyal et al. showed that the union of random spanning trees appro…