KIT | KIT-Bibliothek | Impressum | Datenschutz

A Branch-And-Bound Algorithm for Cluster Editing

Bläsius, Thomas ORCID iD icon 1; Fischbeck, Philipp ; Gottesbüren, Lars 1; Hamann, Michael 1; Heuer, Tobias ORCID iD icon 1; Spinner, Jonas 1; Weyand, Christopher ORCID iD icon 1; Wilhelm, Marcus 1; Schulz, Christian [Hrsg.]; Uçar, Bora [Hrsg.]
1 Karlsruher Institut für Technologie (KIT)


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.

Verlagsausgabe §
DOI: 10.5445/IR/1000149160
Veröffentlicht am 28.07.2022
DOI: 10.4230/LIPIcs.SEA.2022.13
Zitationen: 2
Cover der Publikation
Zugehörige Institution(en) am KIT Institut für Theoretische Informatik (ITI)
Publikationstyp Proceedingsbeitrag
Publikationsjahr 2022
Sprache Englisch
Identifikator ISBN: 978-3-9597725-1-8
ISSN: 1868-8969
KITopen-ID: 1000149160
HGF-Programm 46.21.02 (POF IV, LK 01) Cross-Domain ATMLs and Research Groups
Erschienen in 20th International Symposium on Experimental Algorithms (SEA 2022). Ed.: C. Schulz
Veranstaltung 20th International Symposium on Experimental Algorithms (SEA 2022), Heidelberg, Deutschland, 25.07.2022 – 27.07.2022
Verlag Schloss Dagstuhl - Leibniz-Zentrum für Informatik (LZI)
Seiten Art.-Nr.: 13
Serie Leibniz International Proceedings in Informatics (LIPIcs) ; 233
Externe Relationen Siehe auch
Schlagwörter cluster editing
Nachgewiesen in Scopus
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft
KITopen Landing Page