The Maximum Edge Biclique Problem is NP-Complete

Research output: Book/ReportReportProfessional

432 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

Bicliques
NP-complete problem
Bipartite Graph
Induced Subgraph
Polynomial time
Vertex of a graph

Cite this

Peeters, M. J. P. (2000). The Maximum Edge Biclique Problem is NP-Complete. (FEW Research Memorandum; Vol. 789). Tilburg: Operations research.
Peeters, M.J.P. / The Maximum Edge Biclique Problem is NP-Complete. Tilburg : Operations research, 2000. 5 p. (FEW Research Memorandum).
@book{5f7679c114e1465da2b538a01133047f,
title = "The Maximum Edge Biclique Problem is NP-Complete",
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.",
author = "M.J.P. Peeters",
note = "Pagination: 5",
year = "2000",
language = "English",
volume = "789",
series = "FEW Research Memorandum",
publisher = "Operations research",

}

Peeters, MJP 2000, 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.

Tilburg : Operations research, 2000. 5 p. (FEW Research Memorandum; Vol. 789).

Research output: Book/ReportReportProfessional

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 -

Peeters MJP. The Maximum Edge Biclique Problem is NP-Complete. Tilburg: Operations research, 2000. 5 p. (FEW Research Memorandum).