Exact Perfect Matching in Complete Graphs
Exact Perfect Matching in Complete Graphs
复制标题
完整图中的精确完美匹配
DOI：
10.1145/3041402
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
Thomas Thierauf
中科院分区：
文献类型：
--
作者：
Rohit Gurjar;Arpita Korwar;Jochen Messner;Thomas Thierauf
红蓝图形是一种图形，其中每条边都被涂上红色或蓝色。精确完美匹配问题要求在具有给定数量的红色边的红蓝图中进行完美匹配。我们证明了对于完全图和二部完全图，精确完美匹配问题是与完美匹配问题等价的对数空间。因此，一种高效的完全匹配并行算法将延续到这类图的精确完全匹配问题。我们还报告了在将结果推广到任意图方面的一些进展。
Ared-blue graphis a graph where every edge is colored either red or blue. The exact perfect matching problem asks for a perfect matching in a red-blue graph that has exactly a given number of red edges. We show that for complete and bipartite complete graphs, the exact perfect matching problem is logspace equivalent to the perfect matching problem. Hence, an efficient parallel algorithm for perfect matching would carry over to the exact perfect matching problem for this class of graphs. We also report some progress in extending the result to arbitrary graphs.
登录
查看更多内容
DOI：
--
发表时间：
1987
期刊：
影响因子：
--
作者：
A. Karzanov
通讯作者：
A. Karzanov
DOI：
10.1145/2934310
发表时间：
2012-08
期刊：
ACM Transactions on Computation Theory (TOCT)
影响因子：
--
作者：
R. Gurjar;A. Korwar;J. Messner;Simon Straub;T. Thierauf
通讯作者：
R. Gurjar;A. Korwar;J. Messner;Simon Straub;T. Thierauf
几乎完全匹配
影响因子：
1.1
作者：
R. Yuster
通讯作者：
R. Yuster
彩色二分网络中的匹配
影响因子：
1.1
作者：
Tongnyoul Yi;K. G. Murty;C. Spera
通讯作者：
C. Spera