两分图上的顶点包装

Question

将无向图的每个节点与正权重相关联。这 顶点包装 问题是要找到最大权重的节点子集，以便没有选择两个具有边缘的节点。

解决顶点包装问题的最有效方法是什么 两部分 图形？我能够将其作为最大流量问题提出，并具有两倍的节点数量。是否有更有效的，可能是直接的方法？

Answer 1

好吧，如果VP是顶点覆盖问题的可行解决方案，则P是顶点填料问题的可行解决方案。因此，最大顶点堆积等于最小顶点盖。最小顶点盖反过来等同于两部分图的最大匹配。