A deterministic parallel algorithm for bipartite perfect matching
A deterministic parallel algorithm for bipartite perfect matching
复制标题
一种确定性并行二分完美匹配算法
DOI：
10.1145/3306208
复制
发表时间：
2019
影响因子：
22.7
通讯作者：
Thomas Thierauf
中科院分区：
文献类型：
--
作者：
Stephen A. Fenner;Rohit Gurjar;Thomas Thierauf
计算理论的一个基本探索是理解随机性的力量。目前尚不清楚高效随机化算法的每个问题是否也有一个不使用随机性的问题。在这一主题下被广泛研究的问题之一是完美匹配问题。完美匹配问题有一个基于MulMuley，Vazirani和Vazirani的隔离引理的随机并行(NC)算法。该算法能否去随机化一直是一个悬而未决的问题。本文给出了二部图中完美匹配的隔离引理的一个几乎完全的去随机化。这给出了一个求解二部完美匹配问题的确定性并行(准NC)算法。隔离引理的去随机化意味着我们确定性地构造了一个权重分配，使得最小权重完美匹配是唯一的。我们提出了三种不同的方法来完成这个构造，有一个共同的主要思想。
A fundamental quest in the theory of computing is to understand the power of randomness. It is not known whether every problem with an efficient randomized algorithm also has one that does not use randomness. One of the extensively studied problems under this theme is that of perfect matching. The perfect matching problem has a randomized parallel (NC) algorithm based on the Isolation Lemma of Mulmuley, Vazirani, and Vazirani. It is a long-standing open question whether this algorithm can be derandomized. In this article, we give an almost complete derandomization of the Isolation Lemma for perfect matchings in bipartite graphs. This gives us a deterministic parallel (quasi-NC) algorithm for the bipartite perfect matching problem.Derandomization of the Isolation Lemma means that we deterministically construct a weight assignment so that the minimum weight perfect matching is unique. We present three different ways of doing this construction with a common main idea.
登录
查看更多内容
DOI：
10.1016/s0166-218x(98)00006-7
发表时间：
1998
期刊：
Discret. Appl. Math.
影响因子：
--
作者：
E. Dahlhaus;Marek Karpinski
通讯作者：
Marek Karpinski
DOI：
10.1016/0020-0190(94)00202-a
发表时间：
1995
期刊：
Inf. Process. Lett.
影响因子：
--
作者：
A. Subramanian
通讯作者：
A. Subramanian
客座专栏：完美匹配的并行算法
DOI：
--
发表时间：
2017
期刊：
SIGA
影响因子：
--
作者：
Stephen A. Fenner;R. Gurjar;T. Thierauf
通讯作者：
T. Thierauf
格林定理和平面图中的孤立
DOI：
10.1016/j.ic.2012.03.002
发表时间：
2012
期刊：
Electron. Colloquium Comput. Complex.
影响因子：
--
作者：
Raghunath Tewari;N. V. Vinodchandran
通讯作者：
N. V. Vinodchandran
准NC中的二分完美匹配
DOI：
10.1145/2897518.2897564
发表时间：
2016
期刊：
Proceedings of the forty-eighth annual ACM symposium on Theory of Computing
影响因子：
--
作者：
Stephen A. Fenner;Rohit Gurjar;Thomas Thierauf
通讯作者：
Thomas Thierauf