Guest Column: Parallel Algorithms for Perfect Matching
Guest Column: Parallel Algorithms for Perfect Matching
复制标题
客座专栏：完美匹配的并行算法
DOI：
--
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
T. Thierauf
中科院分区：
文献类型：
--
作者：
Stephen A. Fenner;R. Gurjar;T. Thierauf
完美匹配问题具有基于 Mulmuley、Vazirani 和 Vazirani 的隔离引理的随机 NC 算法。我们给出了隔离引理的几乎完全去随机化，以实现二分图中的完美匹配。这为我们提供了解决二分完美匹配问题的确定性准 NC 算法。
这里提出的轮廓强调了几何观点。我们认为这对于一般图中的完美匹配问题也很有用。
The perfect matching problem has a randomized NC-algorithm based on the Isolation Lemma of Mulmuley, Vazirani and Vazirani. We give an almost complete derandomization of the Isolation Lemma for perfect matchings in bipartite graphs. This gives us a deterministic quasi-NC-algorithm for the bipartite perfect matching problem.
The outline presented here emphasizes a geometric point of view. We think that this will be useful also for the perfect matching problem in general graphs.
准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