The Maximum Edge Biclique Problem is NP-Complete

Research output: Book/ReportReport

479 Downloads (Pure)

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.
Original languageEnglish
Place of PublicationTilburg
PublisherOperations research
Number of pages5
Volume789
Publication statusPublished - 2000

Publication series

NameFEW Research Memorandum
Volume789

Fingerprint Dive into the research topics of 'The Maximum Edge Biclique Problem is NP-Complete'. Together they form a unique fingerprint.

Cite this