KIT | KIT-Bibliothek | Impressum | Datenschutz

PACE solver description: The KaPoCE exact cluster editing algorithm

Bläsius, Thomas ORCID iD icon; Gottesbüren, Lars; Heuer, Tobias ORCID iD icon; Weyand, Christopher; Fischbeck, Philipp; Hamann, Michael; Spinner, Jonas; Wilhelm, Marcus

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.


Verlagsausgabe §
DOI: 10.5445/IR/1000141525
Veröffentlicht am 23.12.2021
Originalveröffentlichung
DOI: 10.4230/LIPIcs.IPEC.2021.27
Scopus
Zitationen: 1
Cover der Publikation
Zugehörige Institution(en) am KIT Institut für Theoretische Informatik (ITI)
Publikationstyp Proceedingsbeitrag
Publikationsjahr 2021
Sprache Englisch
Identifikator ISBN: 978-3-9597721-6-7
ISSN: 1868-8969
KITopen-ID: 1000141525
HGF-Programm 46.21.02 (POF IV, LK 01) Cross-Domain ATMLs and Research Groups
Erschienen in 16th International Symposium on Parameterized and Exact Computation (IPEC 2021). Ed.: P. Golovach
Veranstaltung 16th International Symposium on Parameterized and Exact Computation (IPEC 2021), Lissabon, Portugal, 08.09.2021 – 10.09.2021
Verlag Schloss Dagstuhl - Leibniz-Zentrum für Informatik (LZI)
Seiten Art.-Nr.: 27
Serie Leibniz International Proceedings in Informatics (LIPIcs) ; 214
Nachgewiesen in Scopus
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft
KITopen Landing Page