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 As Get 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
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.