direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Page Content

Graphana - ein erweiterbares Werkzeug zur Messung struktureller Graphparameter

Andreas Fender (Student TU Berlin)
Die parametrisierte Algorithmik ist ein Ansatz für die effiziente Lösung NP-schwerer Probleme. Viele dieser Probleme sind Graphprobleme. Die exponentielle Laufzeit eines Graphproblems wird auf einen sogenannten Graphparameter, welcher Aufschluss über die Struktur des Graphen gibt, beschränkt. Wenn ein Graphparameter auf einer Graphinstanz besonders klein ist, ist das Problem auf dieser dementsprechend effizient lösbar. Eine Weiterentwicklung dieses Konzepts bildet die multivariate Algorithmik: In dieser werden für ein Problem mehrere verschiedene Graphparameter betrachtet und entsprechend mehrere parametrisierte Algorithmen bereitgestellt. Jeder dieser Algorithmen ist jeweils bei bestimmten Graphstrukturen besonders schnell, sodass je nach Struktur des Graphen der passende Algorithmus ausgewählt werden kann.
Den Kern dieser Arbeit bildet das erweiterbare Java-Programm Graphana, mit dem es möglich ist, einige strukturelle Graphparameter zu ermitteln. Auf diese Weise können von einem Graphen die vielversprechendsten Parameter identifiziert werden. Somit kann Graphana beispielsweise als Entscheidungsgrundlage für die Auswahl eines parametrisierten Algorithmus dienen. Weiterhin kann Graphana zur Laufzeitmessung und Visualisierung von Algorithmen verwendet werden. In dieser Arbeit ist eine Anleitung für die grundlegende Benutzung von Graphana sowie eine Beschreibung der implementierten Algorithmen enthalten. Weiterhin wird die Vorgehensweise für das Hinzufügen von Funktionalität erklärt. Abschließend wird im Rahmen einer Fallstudie ein Festparameteralgorithmus für das NP-schwere Maximum Independent Set Problem, parametrisiert mit dem strukturellen Graphparameter Cluster Vertex Deletion Size, vorgestellt.

Zeit
Vortragende
Ort
Sprache
27.10.2011 16:15
Andreas Fender
FR 6510
deutsch

Back to the research colloquium site.

Zusatzinformationen / Extras