论文标题
并联抽样
Sampling Arborescences in Parallel
论文作者
论文摘要
我们研究了从可能加权的有向图中抽样统一的随机定向生根树（也称为树木）的问题。从经典上讲，长期以来，这个问题是可以解决多项式时间的。可以通过决定符[TUT48]计算的确切数量，并且可以将采样简化为计数[JVV86，JS96]。但是，从抽样到计数的经典减少似乎是固有的顺序。这就提出了设计有效的并行算法以进行抽样的问题。我们表明可以在RNC中进行采样杂志。 对于几个良好研究的组合结构，可以将计数简化为确定因素的计算，该确定因素已知在NC中[CSA75]。其中包括轴心，平面图完美匹配，尤拉利亚巡回演出以及确定点过程。但是，对于这些结构的有效平行采样，知之甚少。我们的工作是解决这个谜团的一步。
We study the problem of sampling a uniformly random directed rooted spanning tree, also known as an arborescence, from a possibly weighted directed graph. Classically, this problem has long been known to be polynomial-time solvable; the exact number of arborescences can be computed by a determinant [Tut48], and sampling can be reduced to counting [JVV86, JS96]. However, the classic reduction from sampling to counting seems to be inherently sequential. This raises the question of designing efficient parallel algorithms for sampling. We show that sampling arborescences can be done in RNC. For several well-studied combinatorial structures, counting can be reduced to the computation of a determinant, which is known to be in NC [Csa75]. These include arborescences, planar graph perfect matchings, Eulerian tours in digraphs, and determinantal point processes. However, not much is known about efficient parallel sampling of these structures. Our work is a step towards resolving this mystery.
