Statische und dynamische hierarchische Graphzerlegungen

Graphen, auch Netzwerke genannt, sind ein beliebtes Modell um Beziehungen zwischen Objekten darzustellen. So stellen soziale Netzwerke Beziehungen zwischen Menschen dar, Kommunikationsnetzwerke stellen Verbindungen zwischen technischen Objekten wie zum Beispiel Internetroutern dar und neurologische Netzwerke stellen Verbindungen zwischen Neuronen dar. Das Ziel unseres Projektes ist es, besser zu verstehen, wie verschiedene Berechenbarkeitsprobleme auf Netzwerken gelöst werden können. Solche Probleme sind z.B. Datenpakete durch das Netzwerk zu schicken, im Netzwerk interessante Strukturen, wie zum Beispiel stark miteinander verbundene Untergraphen, sogenannte Cluster, zu finden oder verschiedene andere nützliche Eigenschaften des Netzwerks zu bestimmen. Für viele dieser Berechenbarkeitsprobleme gibt es keine schnellen Algorithmen, um sie exakt zu lösen, und sie werden daher oft nur approximativ, also in Annäherung, gelöst. Unser Ziel ist es, einige wichtige solcher Probleme schneller und mit besserer Approximation zu lösen. Nachdem sich Netzwerke im wirklichen Leben oft ändern, werden wir auch Algorithmen entwickeln, die sich an Veränderungen im Netzwerk anpassen können und nach jeder Veränderung die Antwort neu berechnen und schneller berechnen, als wenn man den Algorithmus von Neuem auf dem ganzen Netzwerk laufen lassen würde. Dabei zerlegen wir den Graphen in Untergraphen, lösen das Problem auf jedem Untergraphen und kombinieren dann diese Lösungen zu einer Lösung für den ganzen Graphen. Man kann sich vorstellen, dass dieser Ansatz aus zwei Schritten besteht: Einer enthält alle Untergraphen, der andere den ganzen Graphen. Um eine hierarchische Graphzerlegung zu erzeugen, wenden wir diesen Ansatz rekursiv auf die Untergraphen an, d.h. wir zerlegen sie wiederum in Unter-Untergraphen etc. Je nachdem welches Berechenbarkeitsproblem auf einem Graphen gelöst werden soll, werden andere Graphzerlegungen benötigt. Für manche Probleme gibt es noch keine derartigen Zerlegungen. Wir werden sowohl neue Graphzerlegungen entwickeln wie auch schnelle Algorithmen, die sie berechnen und sich dynamisch an Veränderungen im Graphen anpassen.