Name
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. |
Year | DOI | Venue |
|---|---|---|
2012 | 10.1007/s00453-010-9486-x | Computing and Combinatorics |
Keywords | Field | DocType |
current o,bipartite graph,convex bipartite graphs,bipartite permutation graph,biconvex graph,convex bipartite graph,graph g,finding maximum edge bicliques,complete bipartite subgraph,maximum edge biclique,maximum edge bicliques,vertex v | Discrete mathematics,Complete bipartite graph,Combinatorics,Edge-transitive graph,Bipartite graph,Chordal bipartite graph,Matching (graph theory),Independent set,Cograph,Mathematics,Strong perfect graph theorem | Journal |
Volume | Issue | ISSN |
64 | 2 | 0178-4617 |
ISBN | Citations | PageRank |
3-642-14030-0 | 7 | 0.51 |
References | Authors | |
28 | 5 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Doron Nussbaum | 1 | 89 | 13.49 |
| Shuye Pu | 2 | 37 | 3.87 |
| Jörg-Rüdiger Sack | 3 | 1099 | 166.07 |
| Takeaki Uno | 4 | 1319 | 107.99 |
| Hamid Zarrabi-Zadeh | 5 | 111 | 13.63 |