License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SEA.2022.13
URN: urn:nbn:de:0030-drops-165473
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/16547/
Bläsius, Thomas ;
Fischbeck, Philipp ;
Gottesbüren, Lars ;
Hamann, Michael ;
Heuer, Tobias ;
Spinner, Jonas ;
Weyand, Christopher ;
Wilhelm, Marcus
A Branch-And-Bound Algorithm for Cluster Editing
Abstract
The cluster editing problem asks to transform a given graph into a disjoint union of cliques by inserting and deleting as few edges as possible. We describe and evaluate an exact branch-and-bound algorithm for cluster editing. For this, we introduce new reduction rules and adapt existing ones. Moreover, we generalize a known packing technique to obtain lower bounds and experimentally show that it contributes significantly to the performance of the solver. Our experiments further evaluate the effectiveness of the different reduction rules and examine the effects of structural properties of the input graph on solver performance. Our solver won the exact track of the 2021 PACE challenge.
BibTeX - Entry
@InProceedings{blasius_et_al:LIPIcs.SEA.2022.13,
author = {Bl\"{a}sius, Thomas and Fischbeck, Philipp and Gottesb\"{u}ren, Lars and Hamann, Michael and Heuer, Tobias and Spinner, Jonas and Weyand, Christopher and Wilhelm, Marcus},
title = {{A Branch-And-Bound Algorithm for Cluster Editing}},
booktitle = {20th International Symposium on Experimental Algorithms (SEA 2022)},
pages = {13:1--13:19},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-251-8},
ISSN = {1868-8969},
year = {2022},
volume = {233},
editor = {Schulz, Christian and U\c{c}ar, Bora},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/16547},
URN = {urn:nbn:de:0030-drops-165473},
doi = {10.4230/LIPIcs.SEA.2022.13},
annote = {Keywords: cluster editing}
}
