The Cluster Editing problem asks to transform a graph into a disjoint union of cliques using a minimum number of edge modifications. Although the problem has been proven NP-complete several times, it has nevertheless attracted much research both from the theoretical and the applied side. The problem has been the inspiration for numerous algorithms in bioinformatics, aiming at clustering entities such as genes, proteins, phenotypes, or patients. In this paper, we review exact and heuristic methods that have been proposed for the Cluster Editing problem, and also applications of these algorithms for biological problems.
Lecture Notes in Computer Science: 9th Conference on Computability in Europe, Cie 2013, Milan, Italy, July, 2013, p. 33-44
Main Research Area:
Lecture Notes in Computer Science
Conference on Computability in EuropeComputability in Europe, 2013