The problem of packing modification-disjoint P3 – an overview and an improved heuristic approach
| dc.contributor.author | Dirks, Jona | |
| dc.contributor.author | Gerhard, Enna | |
| dc.contributor.editor | Gesellschaft für Informatik e.V. | |
| dc.date.accessioned | 2023-02-21T09:39:22Z | |
| dc.date.available | 2023-02-21T09:39:22Z | |
| dc.date.issued | 2022 | |
| dc.description.abstract | 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. | en |
| dc.identifier.isbn | 978-3-88579-752-4 | |
| dc.identifier.pissn | 1614-3213 | |
| dc.identifier.uri | https://dl.gi.de/handle/20.500.12116/40243 | |
| dc.language.iso | en | |
| dc.publisher | Gesellschaft für Informatik, Bonn | |
| dc.relation.ispartof | SKILL 2022 | |
| dc.relation.ispartofseries | Lecture Notes in Informatics (LNI) - Seminars, Volume S-18 | |
| dc.subject | P3 Packing | |
| dc.subject | Cluster Editing | |
| dc.subject | Graph Theory | |
| dc.subject | Heuristic | |
| dc.subject | Complexity | |
| dc.title | The problem of packing modification-disjoint P3 – an overview and an improved heuristic approach | en |
| gi.citation.endPage | 114 | |
| gi.citation.startPage | 103 | |
| gi.conference.date | 29.-30. September 2022 | |
| gi.conference.location | Hamburg | |
| gi.conference.sessiontitle | Theoretische Informatik |
Dateien
Originalbündel
1 - 1 von 1