> Detailanzeige

Bläsius, Thomas [VerfasserIn]; Fischbeck, Philipp [VerfasserIn]; Gottesbüren, Lars [VerfasserIn]; Hamann, Michael [VerfasserIn]; Heuer, Tobias [VerfasserIn]; Spinner, Jonas [VerfasserIn]; Weyand, Christopher [VerfasserIn]; Wilhelm, Marcus [VerfasserIn] ; Thomas Bläsius and Philipp Fischbeck and Lars Gottesbüren and Michael Hamann and Tobias Heuer and Jonas Spinner and Christopher Weyand and Marcus Wilhelm [MitwirkendeR]

A Branch-And-Bound Algorithm for Cluster Editing

Literatur-
verwaltung

Zur
Merkliste

Lösche von
Merkliste

Per Whatsapp teilen

Schließen

Merkliste



Sie können Bookmarks mittels Listen verwalten, loggen Sie sich dafür bitte in Ihr SLUB Benutzerkonto ein.
  • Medientyp: Elektronischer Konferenzbericht; E-Artikel; Sonstige Veröffentlichung
  • Titel: A Branch-And-Bound Algorithm for Cluster Editing
  • Beteiligte: Bläsius, Thomas [VerfasserIn]; Fischbeck, Philipp [VerfasserIn]; Gottesbüren, Lars [VerfasserIn]; Hamann, Michael [VerfasserIn]; Heuer, Tobias [VerfasserIn]; Spinner, Jonas [VerfasserIn]; Weyand, Christopher [VerfasserIn]; Wilhelm, Marcus [VerfasserIn]
  • Erschienen: Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2022
  • Sprache: Englisch
  • DOI: https://doi.org/10.4230/LIPIcs.SEA.2022.13
  • Schlagwörter: cluster editing
  • Entstehung:
  • Anmerkungen: Diese Datenquelle enthält auch Bestandsnachweise, die nicht zu einem Volltext führen.
  • Beschreibung: 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.
  • Zugangsstatus: Freier Zugang