二分钟的快速最大匹配算法

Question

我正在尝试解决以下问题但我的算法太慢了。那是因为我正在使用 edmonds - karp算法找到最大流量当应用于二分的图表时，它也给出了最大匹配。它的运行时间是n ^ 5。我想知道任何更快的算法来解决这个问题（专门的二分钟图）。我目前正在学习的一个算法是 Relabel到Front ，它是n ^ 3。

Answer 1

i使用 Dinitz的算法。还有一个定理，对于最大两分匹配问题的类型的图表，它具有与前面的Relabel相同的复杂性（并且更容易实现）。

在二分匹配问题解决期间产生的网络中， 因此，阶段的数量由O（\ sqrt {v}）界定，因此导致 o（\ sqrt {v} e）绑定时间。得到的算法也被称为 HOPCROFT-KARP算法。更一般地，这种绑定适用于任何单位 网络 - 一个网络，每个顶点，除了源和水槽外， 要么具有一个容量的单个进入边缘，要么是一个 容量的外缘和所有其他容量是任意的 整数。

不幸的是，维基百科关于算法的文章是不够实现它的方式，我无法在线找到更好的资源。我有自己的实施，但很久以前，我已经使用了我大学的其他人的指导。

Answer 2

所谓的匈牙利算法用于二角形匹配可以用较低的运行时实现复杂性。