direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Inhalt des Dokuments

Aleksander Figiel, B.Sc. Informatik

Lupe

Titel der Bachelorarbeit

Parameterized Algorithmics of 2-Club Cluster Graph Modification

Abstract

Wir befassen uns mit drei eng verwandten Graphenmodifikationsproblemen aus der Perspektive der parametrisierten Komplexität. Diese Probleme sind 2-Club Cluster Editing, 2-Club Cluster Vertex Deletion und 2-Club Cluster Edge Deletion, worin es das Ziel ist einen gegebenen Graphen so zu transformieren, dass jede Komponente einen Durchmesser von zwei hat mit der kleinstmöglichen Anzahl eingefügter und gelöschter Kanten, gelöschter Knoten beziehungsweise gelöschter Kanten. Zu den wichtigen Anwendungsgebieten gehört graphbasiertes Clustering--die Aufteilung von Knoten in Cluster, so dass die Knoten in einem Cluster stark miteinander verbunden sind. Eine vorherige Arbeit resultierte in Algorithmen mit Laufzeit O*(3.31^k) beziehungsweise O*(2.74^k) für die letzten zwei Probleme. Wir zeigen ein W[2]-Härte-Ergebnis für 2-Club Cluster Editing, was bedeutet, dass die Existenz eines FPT-Algorithmus sehr unwahrscheinlich ist. Auf der positiven Seite entwickeln wir mehrere Datenreduktionsregeln und untere Schranken für 2-Club Cluster Vertex Deletion und 2-Club Cluster Edge Deletion und implementieren einen Solver für das erste von den beiden. Wir haben erfolgreich Probleminstanzen aus einem biologischen Datensatz mit dichten Graphen bis zu 250 Knoten gelöst.

Zusatzinformationen / Extras

Direktzugang

Schnellnavigation zur Seite über Nummerneingabe

Diese Seite verwendet Matomo für anonymisierte Webanalysen. Mehr Informationen und Opt-Out-Möglichkeiten unter Datenschutz.