从给定的二分图中查找所有最大完全二分子图

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

例如，

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

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

边：A-a、A-b、B-a、B-b、C-c、C-d、D-c、D-d、D-e

最大完全二部为：

{A，B}-{a，b}

{C,D}-{c,d}

{D} - {c、d、e}

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

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

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