论文标题
MV匹配算法的证明
A Proof of the MV Matching Algorithm
论文作者
论文摘要
直到1980年发表\ Cite {MV}，Micali-Vazirani（MV）算法的最大基数匹配，仍然是该问题最有效的已知算法。 本文提供了该算法的第一个完整和正确的证明。我们证明的核心是一些纯图理论事实，捕获了最小长度交替路径的特性；这些可能具有独立的利益。试图使算法更容易理解。
The Micali-Vazirani (MV) algorithm for maximum cardinality matching in general graphs, which was published in 1980 \cite{MV}, remains to this day the most efficient known algorithm for the problem. This paper gives the first complete and correct proof of this algorithm. Central to our proof are some purely graph-theoretic facts, capturing properties of minimum length alternating paths; these may be of independent interest. An attempt is made to render the algorithm easier to comprehend.
