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

Question

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

例如，

顶点集 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)。我不知道是某种近似算法还是随机算法。

Answer 1

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

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