Faster generation of random spanning trees

Details Faster generation of random spanning trees Faster generation of random spanning trees

2009-08-11

arxiv.org/abs/0908.1448v1

Computer Science

Data Structures and Algorithms

Scientific paper

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+\delta)$ of uniform in expected time $\TO(m\sqrt{n}\log 1/\delta)$. This improves the sparse graph case of the best previously known worst-case bound of $O(\min \{mn, n^{2.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.

Affiliated with

Also associated with

No associations

Rating

Faster generation of random spanning trees does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Faster generation of random spanning trees, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Faster generation of random spanning trees will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-164271