### Abstract

Original language | English |
---|---|

Place of Publication | Tilburg |

Publisher | Operations research |

Number of pages | 5 |

Volume | 789 |

Publication status | Published - 2000 |

### Publication series

Name | FEW Research Memorandum |
---|---|

Volume | 789 |

### Fingerprint

### Cite this

*The Maximum Edge Biclique Problem is NP-Complete*. (FEW Research Memorandum; Vol. 789). Tilburg: Operations research.

}

*The Maximum Edge Biclique Problem is NP-Complete*. FEW Research Memorandum, vol. 789, vol. 789, Operations research, Tilburg.

**The Maximum Edge Biclique Problem is NP-Complete.** / Peeters, M.J.P.

Research output: Book/Report › Report › Professional

TY - BOOK

T1 - The Maximum Edge Biclique Problem is NP-Complete

AU - Peeters, M.J.P.

N1 - Pagination: 5

PY - 2000

Y1 - 2000

N2 - 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.

AB - 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.

M3 - Report

VL - 789

T3 - FEW Research Memorandum

BT - The Maximum Edge Biclique Problem is NP-Complete

PB - Operations research

CY - Tilburg

ER -