Var*_*rma 4 algorithm graph matching bipartite network-flow
我试图解决以下问题,但我的算法太慢了.那是因为我使用Edmonds - Karp算法来找到最大流量,当应用于二分图时,它也会产生最大匹配.它的运行时间是n ^ 5.我想知道任何更快的算法来解决这个问题(特别是对于二分图).我目前正在研究的一种算法是Relabel to Front,它是n ^ 3.
我使用迪尼茨算法编写二分匹配.还有一个定理,对于最大二分匹配问题的类型的图,它具有与重新标记相同的复杂性(并且它更容易实现).
在解决二分匹配问题期间出现的网络中,阶段的数量以O(\ sqrt {V})为界,因此导致O(\ sqrt {V} E)时间限制.得到的算法也称为Hopcroft-Karp算法.更一般地说,这种约束适用于任何单位网络 - 其中除了源和宿之外的每个顶点具有容量1的单个进入边缘,或容量1的单个输出边缘,并且所有其他容量是任意整数的网络.
不幸的是,关于该算法的维基百科文章还不足以实现它,我找不到更好的在线资源.我有自己的实现,但是我很久以前就已经使用我大学其他人的指导创建了它.