Find the entire maximum complete bipartite subgraph from a given bipartite graph

Question

This is a bipartite graph, and we want to list the entire maximum complete bipartite subgraph.

For instance,

the set of vertices L = {A, B, C, D}

the set of vertices R = {a, b, c, d, e}

ribs: Aa, Ab, Ba, Bb, Cc, Cd, Dc, Dd, De

Maximum full dicotyledonous:

{A, B} - {a, b}

{C, D} - {c, d}

{D} - {c, d, e}

I found brute force algorithm, O (2 ^ n). I do not know if there is some kind of approximation algorithm or a randomized algorithm.

+5

Colinbinwang Mar 29 '13 at 8:19

1 answer

Jack Cheng · Accepted Answer · 2013-03-29T12:03:05+0000

You can convert the problem into a search for maximum clicks by adding edges between each pair of vertices in each part of the bipartite graph.

- ( ). O (3 ^ (n/3)). .