algorithm - 用于在二部图中找到最大独立顶点集的蛮力算法？

Question

有谁知道用于在二分图中找到最大独立顶点集的蛮力算法的通用轮廓？

我知道还有其他算法，例如用于查找 MIS 的 König 定理，但我想知道蛮力方法的伪代码是什么？

此外，这种蛮力算法的运行时间复杂度是多少？

Answer 1

蛮力算法只是遍历所有顶点集并检查它们是否独立。有2^n一组顶点并遍历所有边以检查独立性O(m)，因此这是成本O(2^n*m)。