Efficient algorithms for cluster editing
| Autor: | Luiz Satoru Ochi, Lucas de Oliveira Bastos, Ivan C. Martins, Rian G. S. Pinheiro, Fábio Protti, Anand Subramanian |
|---|---|
| Rok vydání: | 2014 |
| Předmět: |
021103 operations research
Control and Optimization Theoretical computer science Computer science Efficient algorithm Applied Mathematics Cluster graph GRASP 0211 other engineering and technologies 0102 computer and information sciences 02 engineering and technology 01 natural sciences Graph Computer Science Applications Computational Theory and Mathematics 010201 computation theory & mathematics Theory of computation Discrete Mathematics and Combinatorics Combinatorial optimization Metaheuristic MathematicsofComputing_DISCRETEMATHEMATICS Data reduction |
| Zdroj: | Journal of Combinatorial Optimization. 31:347-371 |
| ISSN: | 1573-2886 1382-6905 |
| DOI: | 10.1007/s10878-014-9756-7 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full text from SpringerLink