LIPIcs.IPEC.2021.27.pdf
- Filesize: 384 kB
- 3 pages
Document
PACE Solver Description: The KaPoCE Exact 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: The KaPoCE Exact Cluster Editing Algorithm. In 16th International Symposium on Parameterized and Exact Computation (IPEC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 214, pp. 27:1-27:3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.IPEC.2021.27
https://doi.org/10.4230/LIPIcs.IPEC.2021.27
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 exact cluster editing algorithm of the KaPoCE framework (contains also a heuristic solver), submitted to the exact track of the 2021 PACE challenge.
Subject Classification
ACM Subject Classification
- Mathematics of computing → Graph algorithms
Keywords
- cluster editing
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.
-
Sebastian Böcker. A golden ratio parameterized algorithm for cluster editing. Journal of Discrete Algorithms, 16:79-89, 2012.
-
Sebastian Böcker, Sebastian Briesemeister, Quang Bao Anh Bui, and Anke Truß. Going weighted: Parameterized algorithms for cluster editing. Theoretical Computer Science, 410(52):5467-5480, 2009.
-
Sebastian Böcker, Sebastian Briesemeister, and Gunnar W Klau. Exact algorithms for cluster editing: Evaluation and experiments. Algorithmica, 60(2):316-334, 2011.
-
Yixin Cao and Jianer Chen. Cluster editing: Kernelization based on edge cuts. Algorithmica, 64(1):152-169, 2012.
- Lars Gottesbüren, Michael Hamann, Philipp Schoch, Ben Strasser, Dorothea Wagner, and Sven Zühlsdorf. Engineering Exact Quasi-Threshold Editing. In 18th International Symposium on Experimental Algorithms (SEA 2020), volume 160, pages 10:1-10:14. Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2020. URL: https://doi.org/10.4230/LIPIcs.SEA.2020.10.
-
Jiong Guo. A more effective linear kernelization for cluster editing. Theoretical Computer Science, 410(8-10):718-726, 2009.