Faster generation of random spanning trees

In this thesis, 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+6) of uniform in expected time ... . This improves the sparse graph case of the best previously known worst-case bound of O(min{mn, n2. 376}), which has stood for twenty years. To achieve this goal, we exploit the connection between random walks on graphs and electrical networks to introduce a new approach to the problem that integrates discrete random walk-based techniques with continuous linear algebraic methods. We believe that our use of electrical networks and sparse linear system solvers in conjunction with random walks and combinatorial partitioning techniques is a useful paradigm that will find further applications in algorithmic graph theory. This work was done in collaboration with Jonathan Kelner.

Department dc:contributor.department

Massachusetts Institute of Technology. Dept. of Electrical Engineering and Computer Science.

Grantor dc:publisher

Massachusetts Institute of Technology

Year dc:date.issued

2009

Author dc:creator

• Ma̧dry, Aleksander

Advisor dc:contributor.advisor

• Jonathan A. Kelner.

• Electrical Engineering and Computer Science.

Statement dc:rights

• M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission.

Licence dc:rights.uri

• http://dspace.mit.edu/handle/1721.1/7582

Language dc:language.iso

eng

Handle dc:identifier.uri

http://hdl.handle.net/1721.1/55126

OAI identifier oai:identifier

oai:dspace.mit.edu:1721.1/55126