LIPIcs.IPEC.2021.28.pdf
- Filesize: 445 kB
- 4 pages
Document
PACE Solver Description: ADE-Solver
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
File
Document Identifiers
Acknowledgements
We want to thank Christian Komusiewicz and Frank Sommer for being our mentors.
Cite AsGet BibTex
Alexander Bille, Dominik Brandenstein, and Emanuel Herrendorf. PACE Solver Description: ADE-Solver. In 16th International Symposium on Parameterized and Exact Computation (IPEC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 214, pp. 28:1-28:4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.IPEC.2021.28
https://doi.org/10.4230/LIPIcs.IPEC.2021.28
Abstract
This document describes our exact solver "ADE" for the unweighted cluster editing problem submitted to the PACE 2021 competition. The solver’s core consists of an FPT-algorithm using a branch and bound strategy in conjunction with several data reduction rules.
Subject Classification
ACM Subject Classification
- Theory of computation → Branch-and-bound
- Mathematics of computing → Graph algorithms
Keywords
- Unweighted 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, 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 Simone Faro and Domenico Cantone, editors, 18th International Symposium on Experimental Algorithms (SEA 2020), volume 160 of Leibniz International Proceedings in Informatics (LIPIcs), pages 10:1-10:14, Dagstuhl, Germany, 2020. Schloss Dagstuhl-Leibniz-Zentrum für Informatik.
-
Jens Gramm, Jiong Guo, Falk Hüffner, and Rolf Niedermeier. Graph-modeled data clustering: Exact algorithms for clique generation. Theory of Computing Systems, 38(4):373-392, 2005.
-
Sepp Hartung and Holger H. Hoos. Programming by optimisation meets parameterised algorithmics: A case study for cluster editing. In Learning and Intelligent Optimization: 9th International Conference, LION 9, Lille, France, January 12-15, 2015. Revised Selected Papers, volume 8994, page 43. Springer, 2015.
-
René van Bevern, Vincent Froese, and Christian Komusiewicz. Parameterizing edge modification problems above lower bounds. Theory of Computing Systems, 62(3):739-770, 2018.