This paper deals with a variant of the well-known Cluster Editing Problem (CEP), more precisely, the  p -CEP, in which a given input graph should be edited by adding and/or removing edges in such a way that  p  vertex-disjoint cliques (clusters) are generated with the minimum number of editions. We introduce several valid inequalities where some of them turned out to be very effective when implemented in branch-and-cut approaches over two mathematical formulations. Computational experiments were carried out over a set of instances available in the CEP literature. The results obtained show the efficiency of the approaches according to the value of  p , the graph density and the ratio between  p  and the number of vertices.
['Teobaldo Bulhões', 'Gilberto Farias de Sousa Filho', 'Anand Subramanian', 'Lucídio dos Anjos Formiga Cabral']
Branch-and-cut approaches for p-Cluster Editing