Abstract | ||
---|---|---|
The cluster editing problem consists of transforming an input graph \(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. |
Year | DOI | Venue |
---|---|---|
2016 | 10.1007/s10878-014-9756-7 | Journal of Combinatorial Optimization |
Keywords | Field | DocType |
Combinatorial optimization, Cluster editing, Data reduction, Metaheuristics, Exact methods, Hybrid algorithms | Graph,Mathematical optimization,Heuristic,Coupling,GRASP,Computer science,Algorithm,Combinatorial optimization,Theoretical computer science,Disjoint union,Metaheuristic,Data reduction | Journal |
Volume | Issue | ISSN |
31 | 1 | 1573-2886 |
Citations | PageRank | References |
9 | 0.53 | 16 |
Authors | ||
6 |
Name | Order | Citations | PageRank |
---|---|---|---|
Lucas de O. Bastos | 1 | 12 | 1.02 |
Luiz Satoru Ochi | 2 | 474 | 34.62 |
Fábio Protti | 3 | 357 | 46.14 |
Anand Subramanian | 4 | 1154 | 58.21 |
Ivan C. Martins | 5 | 20 | 2.14 |
Rian G. S. Pinheiro | 6 | 31 | 4.72 |