Logo des Repositoriums

S18 - SKILL 2022 - Studierendenkonferenz Informatik

https://dl.gi.de/handle/20.500.12116/40229
Auflistung nach:

Auflistung S18 - SKILL 2022 - Studierendenkonferenz Informatik nach Schlagwort "Complexity"

1 - 1 von 1
  • Textdokument
    The problem of packing modification-disjoint P3 – an overview and an improved heuristic approach
    (SKILL 2022, 2022) Dirks, Jona; Gerhard, Enna
    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.