Faster Generation of Random Spanning Trees
Faster Generation of Random Spanning Trees
复制标题
更快地生成随机生成树
DOI：
10.1109/focs.2009.75
复制
发表时间：
2009
期刊：
影响因子：
--
通讯作者：
A. Madry
中科院分区：
文献类型：
--
作者：
Jonathan A. Kelner;A. Madry
在本文中，我们提出了一种新算法，用于在无向图中生成大约均匀的随机跨越树。我们展示了如何从预期时间$ \ to（m \ sqrt {n} \ log 1/\ delta）$中的乘法$（1+ \ delta）$中的分布中进行采样。这改善了$ o（\ min \ {mn，n^{2.376} \}）$的稀疏图案例，已持续了二十年。为了实现这一目标，我们利用图形和电网上随机步行之间的连接，并使用它来引入一种新的方法，以将离散的随机步行技术与连续的线性代数方法整合在一起。我们认为，我们将电网和稀疏线性系统求解器与随机步行和组合分区技术结合使用是一个有用的范式，它将在算法图理论中找到进一步的应用。
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.