带权顶点的二分图最大权匹配

Question

3

我有一个二分图，其中有两组顶点A和B。边没有权重。但是，其中一组顶点（称为集合B）被赋予正权重(wb1,wb2...)。我想在这个二分图中找到一个匹配，以最大化匹配自集合B中顶点的权重之和。

经过广泛的在线搜索，我得出了以下结论：将所有与顶点bi相邻的边都标记为权重wbi，然后运行匈牙利算法。

是否有更有效的方法来解决这个问题？因为它与加权最大匹配不同（这里顶点具有权重而不是边）。

如果我的语言不够清晰，请随意修改。谢谢。

- newguy

您IP地址为143.198.54.68，由于运营成本限制，当前对于免费用户的使用频率限制为每个IP每72小时10次对话，如需解除限制，请点击左下角设置图标按钮（手机用户先点击左上角菜单按钮）。 - shapiro yaacov

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- David Eisenstat · Accepted Answer

如果将时间复杂度从O(V^3)降低到O(VE)，并采用更简单的算法（对于最密集的图形来说，渐近复杂度不是最优的），您可以利用匹配的拟阵结构，方法如下：通过重复选择一条通向B中未匹配顶点的路径，并且该路径的权值尽可能大，实例化Ford--Fulkerson算法。