A bipartite graph G=(A, B, E) is convex on B if there exists an ordering of the vertices of B such that for any vertex v εA, vertices adjacent to v are consecutive in B. A complete bipartite subgraph of a graph G is called a biclique of G. In this paper, we study the problem of finding the maximum edge-cardinality biclique in convex bipartite graphs. Given a bipartite graph G=(A, B, E) which is convex on B, we present a new algorithm that computes the maximum edge-cardinality biclique of G in O(n log3 n loglogn) time and O(n) space, where n=|A|. This improves the current O(n 2) time bound available for the problem.

Additional Metadata
Persistent URL dx.doi.org/10.1007/978-3-642-14031-0_17
Citation
Nussbaum, D, Pu, S. (Shuye), Sack, J.-R, Uno, T. (Takeaki), & Zarrabi-Zadeh, H. (Hamid). (2010). Finding maximum edge bicliques in convex bipartite graphs. doi:10.1007/978-3-642-14031-0_17