Faster generation of random spanning trees

Faster generation of random spanning trees

Show other versions (1)

In this paper, we set forth a new algorithm for generating approximately uniformly random spanning trees in undirected graphs. We show how to sample from a distribution that is within a multiplicative (1+ d) of uniform in expected time O[over-(m[sqrt]n log 1/d).This improves the sparse graph case of...

Full description

Bibliographic Details
Main Authors: Kelner, Jonathan Adam, Madry, Aleksander
Other Authors: Massachusetts Institute of Technology. Department of Mathematics
Format: Article
Language:en_US
Published: Institute of Electrical and Electronics Engineers 2010
Subjects:
spanning trees
random walks on graphs
electrical flows
Online Access:http://hdl.handle.net/1721.1/59437
https://orcid.org/0000-0003-0536-0323
https://orcid.org/0000-0002-4257-4198

Internet

http://hdl.handle.net/1721.1/59437
https://orcid.org/0000-0003-0536-0323
https://orcid.org/0000-0002-4257-4198

Similar Items