Textdokument
The problem of packing modification-disjoint P3 – an overview and an improved heuristic approach
Vorschaubild nicht verfügbar
Volltext URI
Dokumententyp
Dateien
Datum
2022
Autor:innen
Zeitschriftentitel
ISSN der Zeitschrift
Bandtitel
Quelle
SKILL 2022
Theoretische Informatik
Verlag
Gesellschaft für Informatik, Bonn
Zusammenfassung
The problem of packing modification-disjoint P₃ – an overview and an improved heuristic approach We consider the problem of packing modification-disjoint induced P₃. This has not been fully researched so far. Induced P₃ are especially relevant to solve the cluster editing problem. We provide an overview and new insights for locating modification-disjoint P₃ packing within the complexity hierarchy. Accordingly, we further look into conflict graphs. In response to our theoretical results, we create a significantly improved heuristic based on the approach of Spinner (2019). We then analyze its efficiency empirically on a selection of generated and public datasets. Our results show that it is either better than existing heuristics when comparing solution size and running time.