Given is a bipartite graph, and we want to list all maximal complete bipartite sub-graph.
For instance,
vertex set L = {A, B, C, D}
vertex set R = {a, b, c, d, e}
edges: A-a, A-b, B-a, B-b, C-c, C-d, D-c, D-d, D-e
The maximal complete bipartite are:
{A,B}-{a, b}
{C,D}-{c, d}
{D} - {c, d, e}
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.
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.