The maximum edge biclique problem is NP-complete
| Author(s) : | Ren?? Peeters, |
| Publisher : | N/A |
| Publication Date : | 2003 |
| ISSN : | N/A |
| Abstract : | We prove that the maximum edge biclique problem in bipartite graphs is NP-complete. A biclique in a bipartite graph is a vertex induced subgraph which is complete. The problem of finding a biclique with a maximum number of vertices is known to be solvable in polynomial time but the complexity of finding a biclique with a maximum number of edges was still undecided. 1, |