Is there an efficient (say in O(|V|^2)) and preferably not overly complicated algorithm for dividing a bipartite graph into the smallest possible number of bicliques? The vertices can repeat, so that all of the edges are contained.
I tried searching for it but couldn't understand some papers on this topic.
I'll be grateful for any help :)
In the mathematical fields of graph theory and combinatorial optimization, the bipartite dimension or biclique cover number of a graph G = (V, E) is the minimum number of bicliques (that is complete bipartite subgraphs), needed to cover all edges in E. A collection of bicliques covering all edges in G is called a biclique edge cover, or sometimes biclique cover. The bipartite dimension of G is often denoted by the symbol d(G).
I'd like help efficiently finding a biclique cover that realizes d(G) for an input bipartite graph G.