Fast algorithms for finding the maximum edge cardinality biclique in convex bipartite graphs

The problem of finding the maximum edge cardinality biclique (MECB) in convex bipartite graphs has been studied in the context of biclustering analysis of gene expression data matrices. A bipartite graph G = ( A, B, E), where A and B represent the bipartitions of the vertex set and E denotes the edge set, is convex on B if there is an ordering of B such that the neighborhood of each vertex in A forms a consecutive interval on B. A biclique is a complete bipartite subgraph. We found that the number of maximal bicliques in a B-convex bipartite graph is O(|A| 2). We designed and analyzed two algorithms, BICLIQUE_DOMA and BICLIQUE_DOM, to find MECB in a convex bipartite graph. Algorithm BICLIQUE_DOMA takes O(dmax(B)|A |) time and uses O(|A|) space, where dmax(B) is the maximum degree of B; with minor modifications, this algorithm can also be used to list all maximal bicliques in convex bipartite graphs. Algorithm BICLIQUE_DOM runs in time O(|B|2 + |A|) and requires O(| B| + |A|) space. We also designed and analyzed algorithms BICLIQUE_MAAPR and BICLIQUE_PERM for finding MECB in doubly convex bipartite graphs and bipartite permutation graphs, respectively. While BICLIQUE_MAAPR runs almost in time linear in |A|, BICLIQUE_PERM's run time is linear in |A|, which is optimal. Both algorithms use O(|A|) storage space. These algorithms were implemented and tested subsequently. Our experimental results agree with those of the theoretical analysis. These algorithms represent the best solutions up-to-date to the problem of finding MECB in convex bipartite graphs.