从给定的二分图中找到所有最大的完整二分图 [英] Find all maximal complete bipartite subgraph from given bipartite graph

问题描述

给定是一个二部图，我们要列出所有最大的完整二部图。

Given is a bipartite graph, and we want to list all maximal complete bipartite sub-graph.

例如，

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

vertex set L = {A, B, C, D}

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

vertex set R = {a, b, c, d, e}

边：Aa，Ab，Ba，Bb，Cc，Cd，Dc，Dd，De

edges: A-a, A-b, B-a, B-b, C-c, C-d, D-c, D-d, D-e

最大二分法是：

{A，B}-{a，b}

{A,B}-{a, b}

{C，D}- {c，d}

{C,D}-{c, d}

{D}-{c，d，e}

{D} - {c, d, e}

我发现了一个蛮力算法O（2 ^ n）。
我不知道是某种近似算法还是随机算法。

I have found a brute force algorithm, O(2^n). I don't know if some approximation algorithm or randomized algorithm.

推荐答案

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

You can transform the problem to finding maximal cliques by adding edges between every pair of vertices in each part of the bipartite graph.

Bron-Kerbosch算法可用于列出图中的所有最大组（不是必然是两方的）。它非常容易实现，并且在最坏情况下的时间界限为O（3 ^（n / 3））。图的简并性还存在一个固定参数易处理的时间限制。

The Bron-Kerbosch algorithm can be used to list all maximal cliques in a graph (not necessarily bipartite). It is pretty easy to implement and has a slightly better worst-case time bound of O(3^(n/3)). There is also a fix-parameter tractable time bound in term of the degeneracy of the graph.

这篇关于从给定的二分图中找到所有最大的完整二分图的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！