Title: Finding Maximum Edge Bicliques in Convex Bipartite Graphs
Abstract: 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.