Faster Generation of Random Spanning Trees
Authors:
- Jonathan A. KelnerJKJonathan A. Kelner
- Aleksander MadryAMAleksander Madry
- 1 October 2009
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 02725428,p. 13-21
Abstract
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+ ¿) of uniform in expected time O¿(m¿n log 1/¿). 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, and we use this 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.Keywords
All Related Versions
This publication has 16 references indexed in Scilit:
- Twice-ramanujan sparsifiers2009
- Expanders via Random Spanning Trees2009
- Graph sparsification by effective resistances2008
- Approximation Algorithms for Unique Games2005
- Multicommodity max-flow min-cut theorems and their use in designing approximation algorithmsJournal of the ACM, 1999
- Shuffling biological sequencesDiscrete Applied Mathematics, 1996
- Generating random combinatorial objectsJournal of Algorithms, 1990
- Unranking and ranking spanning trees of a graphJournal of Algorithms, 1989
- Random spanning treeJournal of Algorithms, 1983
- Graph Theory1979