LIPIcs.IPEC.2021.31.pdf
- Filesize: 439 kB
- 4 pages
Document
PACE Solver Description: KaPoCE: A Heuristic Cluster Editing Algorithm
Authors
-
Part of:
Volume:
16th International Symposium on Parameterized and Exact Computation (IPEC 2021)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: International Symposium on Parameterized and Exact Computation (IPEC) - License:
Creative Commons Attribution 4.0 International license
- Publication Date: 2021-11-22
Cite AsGet BibTex
Thomas Bläsius, Philipp Fischbeck, Lars Gottesbüren, Michael Hamann, Tobias Heuer, Jonas Spinner, Christopher Weyand, and Marcus Wilhelm. PACE Solver Description: KaPoCE: A Heuristic Cluster Editing Algorithm. In 16th International Symposium on Parameterized and Exact Computation (IPEC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 214, pp. 31:1-31:4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.IPEC.2021.31
https://doi.org/10.4230/LIPIcs.IPEC.2021.31
Abstract
The cluster editing problem is to transform an input graph into a cluster graph by performing a minimum number of edge editing operations. A cluster graph is a graph where each connected component is a clique. An edit operation can be either adding a new edge or removing an existing edge. In this write-up we outline the core techniques used in the heuristic cluster editing algorithm of the Karlsruhe and Potsdam Cluster Editing (KaPoCE) framework, submitted to the heuristic track of the 2021 PACE challenge.
Subject Classification
ACM Subject Classification
- Mathematics of computing → Graph algorithms
Keywords
- cluster editing
- local search
- variable neighborhood search
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
-
Lucas Bastos, Luiz Satoru Ochi, Fábio Protti, Anand Subramanian, Ivan César Martins, and Rian Gabriel S Pinheiro. Efficient Algorithms for Cluster Editing. Journal of Combinatorial Optimization, 31(1):347-371, 2016.
- Thomas Bläsius, Philipp Fischbeck, Lars Gottesbüren, Michael Hamann, Tobias Heuer, Jonas Spinner, Christopher Weyand, and Marcus Wilhelm. KaPoCE - An Exact and Heuristic Solver for the Cluster Editing Problem. https://github.com/kittobi1992/cluster_editing/tree/pace-2021, 2021. URL: https://doi.org/10.5281/zenodo.4892524.
-
Pierre Hansen and Nenad Mladenović. Variable Neighborhood Search. In Handbook of Metaheuristics, pages 145-184. Springer, 2003.
-
George Karypis and Vipin Kumar. Multilevel k-way Hypergraph Partitioning. Technical Report 98-036, University of Minnesota, 1998.
-
Usha Nandini Raghavan, Réka Albert, and Soundar Kumara. Near Linear Time Algorithm to Detect Community Structures in Large-Scale Networks. Physical Review E, 76(3):036106, 2007.