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

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))。就图的简并性而言，还有一个固定参数的易处理时间界限。