Efficient algorithms for cluster editing

Lucas Bastos, Luiz Satoru Ochi, Fábio Protti, Anand Subramanian (), Ivan César Martins and Rian Gabriel S. Pinheiro
Additional contact information
Lucas Bastos: Praia do Flamengo 200 - 1ºandar
Luiz Satoru Ochi: Instituto de Computação
Fábio Protti: Instituto de Computação
Anand Subramanian: Departamento de Engenharia de Produção
Ivan César Martins: Instituto de Computação
Rian Gabriel S. Pinheiro: Instituto de Computação

Journal of Combinatorial Optimization, 2016, vol. 31, issue 1, No 23, 347-371

Abstract: Abstract The cluster editing problem consists of transforming an input graph $$G$$ G into a cluster graph (a disjoint union of complete graphs) by performing a minimum number of edge editing operations. Each edge editing operation consists of either adding a new edge or removing an existing edge. In this paper we propose new theoretical results on data reduction and instance generation for the cluster editing problem, as well as two algorithms based on coupling an exact method to, respectively, a GRASP or ILS heuristic. Experimental results show that the proposed algorithms are able to find high-quality solutions in practical runtime.

Keywords: Combinatorial optimization; Cluster editing; Data reduction; Metaheuristics; Exact methods; Hybrid algorithms (search for similar items in EconPapers)
Date: 2016
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (5)

Downloads: (external link)
http://link.springer.com/10.1007/s10878-014-9756-7 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:31:y:2016:i:1:d:10.1007_s10878-014-9756-7

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-014-9756-7

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().