Logo des Repositoriums
 

The problem of packing modification-disjoint P3 – an overview and an improved heuristic approach

dc.contributor.authorDirks, Jona
dc.contributor.authorGerhard, Enna
dc.contributor.editorGesellschaft für Informatik e.V.
dc.date.accessioned2023-02-21T09:39:22Z
dc.date.available2023-02-21T09:39:22Z
dc.date.issued2022
dc.description.abstractThe 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.en
dc.identifier.isbn978-3-88579-752-4
dc.identifier.pissn1614-3213
dc.identifier.urihttps://dl.gi.de/handle/20.500.12116/40243
dc.language.isoen
dc.publisherGesellschaft für Informatik, Bonn
dc.relation.ispartofSKILL 2022
dc.relation.ispartofseriesLecture Notes in Informatics (LNI) - Seminars, Volume S-18
dc.subjectP3 Packing
dc.subjectCluster Editing
dc.subjectGraph Theory
dc.subjectHeuristic
dc.subjectComplexity
dc.titleThe problem of packing modification-disjoint P3 – an overview and an improved heuristic approachen
gi.citation.endPage114
gi.citation.startPage103
gi.conference.date29.-30. September 2022
gi.conference.locationHamburg
gi.conference.sessiontitleTheoretische Informatik

Dateien

Originalbündel
1 - 1 von 1
Vorschaubild nicht verfügbar
Name:
A4-1.pdf
Größe:
254.03 KB
Format:
Adobe Portable Document Format