An almost-linear time algorithm for uniform random spanning tree generation
An almost-linear time algorithm for uniform random spanning tree generation
复制标题
均匀随机生成树生成的近线性时间算法
DOI：
10.1145/3188745.3188852
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
Aaron Schild
中科院分区：
文献类型：
--
作者：
Aaron Schild
我们给出了一个 m1+o(1)βo(1) 时间算法，用于在具有最大与最小权重比 β 的加权图中生成均匀随机生成树。在此过程中，我们将说明如何通过使用相关拉普拉斯矩阵的 Schur 补从图中消除顶点来克服图划分中的基本权衡。我们的起点是 Aldous-Broder 算法，该算法使用随机游走对随机生成树进行采样。与之前的工作一样，我们使用快速拉普拉斯线性系统求解器来缩短从顶点 v 到分配给 v 的一组顶点的边界的随机游走，称为“捷径”。我们与之前的工作不同，引入了一种使用拉普拉斯求解器来缩短步行路程的新方法。为了限制捷径工作量，我们证明大多数随机游走步骤发生在远离未访问顶点的地方。我们通过将捷径 S 的使用收费到 Schur 补集中的随机游走步骤来应用这一观察，该 Schur 补集是通过消除 S 中未分配给它的所有顶点而获得的。
We give an m1+o(1)βo(1)-time algorithm for generating uniformly random spanning trees in weighted graphs with max-to-min weight ratio β. In the process, we illustrate how fundamental tradeoffs in graph partitioning can be overcome by eliminating vertices from a graph using Schur complements of the associated Laplacian matrix. Our starting point is the Aldous-Broder algorithm, which samples a random spanning tree using a random walk. As in prior work, we use fast Laplacian linear system solvers to shortcut the random walk from a vertex v to the boundary of a set of vertices assigned to v called a “shortcutter.” We depart from prior work by introducing a new way of employing Laplacian solvers to shortcut the walk. To bound the amount of shortcutting work, we show that most random walk steps occur far away from an unvisited vertex. We apply this observation by charging uses of a shortcutter S to random walk steps in the Schur complement obtained by eliminating all vertices in S that are not assigned to it.
DOI：
10.1109/focs.2017.90
发表时间：
2017-05
期刊：
2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS)
影响因子：
--
作者：
D. Durfee;John Peebles;Richard Peng;Anup B. Rao
通讯作者：
D. Durfee;John Peebles;Richard Peng;Anup B. Rao