在给定最大匹配的情况下找到二分图的最小顶点覆盖

Question

我似乎找到了一个算法,但我很难理解它,我想知道你们中是否有人知道算法的通用轮廓.

这是我在第2页找到的算法的链接

http://www.cse.iitb.ac.in/~sundar/cs435/lecture23.pdf

Answer 1

算法很简单:

1. 找到不匹配的顶点,将其标记为不包含在最小顶点覆盖中.
2. 将此顶点的所有匹配邻居标记为包含在最小顶点覆盖中.
3. 将前一步骤中所有顶点的配合视为不匹配的顶点,并重复步骤1.
4. 如果递归结束,则从步骤1开始重复(即图的几个连接组件的情况).
5. 如果没有不匹配的顶点,则取所有剩余的对并以您喜欢的方式标记它们(请记住,对中的一个顶点必须包含在最小顶点覆盖中,而其他顶点必须不包括在内).

PS我知道这是necroposting.