algorithm - 与加权顶点的最大权重二分匹配

Question

我有一个包含两组顶点 A 和 B 的二分图。边没有权重。但是，其中一个集合(比如集合 B)中的顶点分配有正权重(wb1，wb2 ...)我想在这个二分图中找到一个匹配，以最大化从集合 B 匹配的顶点的权重之和。

经过广泛的在线搜索后，这就是我想出的:为顶点 bi 上的所有边分配权重 wbi 并运行匈牙利算法。有没有更有效的方法来看待这个问题，因为它不同于加权最大匹配(这里顶点有权重而不是边)

如果我的语言不清楚，请随时编辑。谢谢。

Answer 1

如果从 O(V^3) 到 O(V E) 的改进和更简单的算法是值得的(对于最密集的图它不是渐近的)，您可以按如下方式利用匹配的拟阵结构。实例化 Ford--Fulkerson通过重复选择到 B 中权重尽可能大的不匹配顶点的路径。