TL;DR本文提出了一种基于随机算法和修剪的自适应均匀采样策略，在 O (n log n) 时间内寻找 d - 正则图中完美匹配，并用于求解双随机矩阵的 Birkhoff-von Neumann 分解。
Abstract
In this paper we consider the well-studied problem of finding a perfect
matching in a d-regular bipartite graph on 2n nodes with m=nd edges. The
best-known algorithm for general bipartite graphs (due to Hopcroft and Karp)
takes time O(m\sqrt{n}). In regular bipartite graphs, however, a
本研究考虑图的两个极大 / 完美匹配的对称差至少为 k 的多样化匹配问题，并表明当 k 是输入的一部分时，在一般图上多样性匹配 (请求两个不必须是最大或完美匹配) 是 NP 完全的。然后探讨两个限制变量：首先，对于二分图，问题可以在多项式时间内解决；其次，Diverse Pair of Maximum Matchings 可以通过 FPT 参数 k 来解决。最后表明 Diverse Pair of Matchings 在 Ο$(k^2)$ 顶点上有一个核心。