algorithm - 从给定的二部图中找到所有最大的完全二部子图

Question

给定一个二部图，我们要列出所有最大完全二部子图。

例如，

顶点集 L = {A, B, C, D}

顶点集 R = {a, b, c, d, e}

边缘：Aa、Ab、Ba、Bb、Cc、Cd、Dc、Dd、De

最大完全二分是：

{A,B}-{a,b}

{C,D}-{c,d}

{D} - {c, d, e}

我找到了一个蛮力算法，O(2^n)。我不知道是一些近似算法还是随机算法。

Answer 1

您可以通过在二分图的每个部分的每对顶点之间添加边来将问题转换为找到最大团。

Bron-Kerbosch 算法可用于列出图中的所有最大团（不一定是二分的）。它很容易实现，并且在 O(3^(n/3)) 的最坏情况下的时间界限稍好一些。就图的退化而言，还有一个固定参数的可处理时间界限。