Dirks, JonaGerhard, EnnaGesellschaft für Informatik e.V.2023-02-212023-02-212022978-3-88579-752-4https://dl.gi.de/handle/20.500.12116/40243The 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.enP3 PackingCluster EditingGraph TheoryHeuristicComplexityThe problem of packing modification-disjoint P3 – an overview and an improved heuristic approach1614-3213