Bipartite perfect matching is in quasi-NC
Bipartite perfect matching is in quasi-NC
复制标题
准NC中的二分完美匹配
DOI：
10.1145/2897518.2897564
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
Thomas Thierauf
中科院分区：
文献类型：
--
作者：
Stephen A. Fenner;Rohit Gurjar;Thomas Thierauf
我们证明了二部完美匹配问题在拟NC2中。也就是说，它具有拟多项式大小为O(Logn)，深度为Ando(Log2n)的均匀回路。以前，关于多对数深度的电路的大小只有一个指数上界，我们通过对著名的隔离引理进行几乎完全的去随机化得到了我们的结果，当应用于二部完美匹配问题时，我们得到了一个有效的随机并行算法。
We show that the bipartite perfect matching problem is in quasi-NC2. That is, it has uniform circuits of quasi-polynomial sizenO(logn), andO(log2n) depth. Previously, only an exponential upper bound was known on the size of such circuits with poly-logarithmic depth.We obtain our result by an almost complete derandomization of the famous Isolation Lemma when applied to yield an efficient randomized parallel algorithm for the bipartite perfect matching problem.
登录
查看更多内容
DOI：
10.1016/s0166-218x(98)00006-7
发表时间：
1998
期刊：
Discret. Appl. Math.
影响因子：
--
作者：
E. Dahlhaus;Marek Karpinski
通讯作者：
Marek Karpinski
格林定理和平面图中的孤立
DOI：
10.1016/j.ic.2012.03.002
发表时间：
2012
期刊：
Electron. Colloquium Comput. Complex.
影响因子：
--
作者：
Raghunath Tewari;N. V. Vinodchandran
通讯作者：
N. V. Vinodchandran
DOI：
--
发表时间：
2016
期刊：
影响因子：
--
作者：
V. Faber;David G. Harris
通讯作者：
David G. Harris
平面完美匹配位于 NC
DOI：
--
发表时间：
2017
期刊：
arXiv.org
影响因子：
--
作者：
P. Sankowski
通讯作者：
P. Sankowski
DOI：
10.1002/jgt.3190160103
发表时间：
1992
期刊：
J. Graph Theory
影响因子：
--
作者：
C. Teo;K. Koh
通讯作者：
K. Koh