graph-theory - 二部图上的顶点打包

Question

将无向图的每个节点与正权重相关联。顶点打包问题是找到具有最大权重和的节点的子集，这样就不会选择两个节点之间有一条边。

解决二部图的顶点打包问题的最有效方法是什么？我已经能够将其表述为具有两倍节点数的最大流量问题。有没有更有效、可能更直接的方法？

Answer 1

好吧，当 VP 是顶点覆盖问题的可行解时，P 是顶点打包问题的可行解。因此，最大顶点封装等价于最小顶点覆盖。反过来，最小顶点覆盖相当于二分图的最大匹配。