Finding Maximum Edge Bicliques in Convex Bipartite Graphs |
| |
Authors: | Doron Nussbaum Shuye Pu J?rg-Rüdiger Sack Takeaki Uno Hamid Zarrabi-Zadeh |
| |
Affiliation: | 1. School of Computer Science, Carleton University, Ottawa, ON, K1S 5B6, Canada 2. Program in Molecular Structure and Function, Hospital for Sick Children, 555 University Avenue, Toronto, ON, M5G 1X8, Canada 3. National Institute of Informatics, 2-1-2 Hitotsubashi, Chiyoda-ku, Tokyo, 101-8430, Japan 4. Department of Computer Engineering, Sharif University of Technology, Tehran, Iran
|
| |
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. Motivated by an application to analyzing DNA microarray data, we study the problem of finding maximum edge bicliques in convex bipartite graphs. Given a bipartite graph G=(A,B,E) which is convex on B, we present a new algorithm that computes a maximum edge biclique of G in O(nlog?3 nlog?log?n) time and O(n) space, where n=|A|. This improves the current O(n 2) time bound available for the problem. We also show that for two special subclasses of convex bipartite graphs, namely for biconvex graphs and bipartite permutation graphs, a maximum edge biclique can be computed in O(n??(n)) and O(n) time, respectively, where n=min?(|A|,|B|) and ??(n) is the slowly growing inverse of the Ackermann function. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|