Optimization Online


Branch-and-Cut approaches for p-Cluster Editing

Teobaldo Bulhões(tbulhoes***at***ic.uff.br)
Gilberto Sousa(gilberto***at***ci.ufpb.br)
Anand Subramanian(anand***at***ct.ufpb.br)
Lucídio Cabral(lucidio***at***ci.ufpb.br)

Abstract: This paper deals with a variant of the well-known Cluster Editing Problem (CEP), more precisely, the \textit{p}-CEP, in which a given input graph should be edited by adding and/or removing edges in such a way that \textit{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 \textit{p}, the graph density and the ratio between \textit{p} and the number of vertices.

Keywords: Cluster Editing , Valid Inequalities , Branch-and-cut

Category 1: Combinatorial Optimization (Branch and Cut Algorithms )

Citation: Working Paper, UFPB

Download: [PDF]

Entry Submitted: 05/26/2016
Entry Accepted: 06/01/2016
Entry Last Modified: 05/26/2016

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society