Footnote:
Diese Datenquelle enthält auch Bestandsnachweise, die nicht zu einem Volltext führen.
Description:
Ein F-freier Graph besitzt keinen induzierten Teilgraphen aus einer Menge von verbotenen Teilgraphen F. Man kann Kanten in einem Graphen editieren (einfügen oder entfernen) um einen Graphen zu erreichen, der F-frei ist. Das Ziel von F-free Edge Editing ist es, eine minimale Menge an Editierungsoperation zu finden, die zu einem F-freien Graphen führen. Wir betrachten eine Generalisierung, Weighted F-free Edge Editing, die beliebige Kosten für die Editierungsoperationen erlaubt. In dieser Arbeit fokussieren wir uns auf einen parametrisierten Suchbaumalgorithmus (FPT) mit den Editierungskosten als Parameter. Wir adaptieren bereits existierende Beschleunigungstechniken für das ungewichteten Editieren für den gewichteten Fall. Unter anderem betrachten wir Algorithmen zum Berechnen von unteren Schranken und Strategien für die Auswahl von Teilgraphen zum Verzweigen. Außerdem diskutieren wir das Problem, die optimalen Editierungskosten für den Suchbaumalgorithmus zu finden und präsentieren dafür zwei neue Suchstrategien. Zusätzlich behandeln wir einen Algorithmus basierend auf ganzahliger linearer Optimierung (ILP) und Methoden, die die Anzahl der generierten Bedingungen beschränken. Des Weiteren evaluieren wir die FPT und ILP Algorithmen und ihre Beschleunigungstechniken auf Protein-Protein Interaktionsgraphen für F = {C4, P4}. Wir stellen fest, dass der FPT Algorithmus am meisten von dem Greedy-Algorithmus für untere Schranken und der Auswahlstrategie “most adjacent” profitiert. Letztere präferiert Teilgraphen, die zu vielen anderen verbotenen Teilgraphen adjazent sind. Auch fanden wir heraus, dass der Algorithmus für die untere Schranken, der auf lokaler Suche basiert, im gewichteten Fall größere Probleme mit lokalen Maxima hat. Weiterhin bemerken wir, dass das Beschränken der Anzahl der generierten Bedingungen den ILP Algorithmus signifikant schneller werden lässt. Schlussendlich haben wir beide Lösungsalgorithmen verglichen und kamen zum Schluss, dass der ILP Algorithmus konsistent besser ist als der FPT ...