Komplexe Graphen bzw. Netzwerke treten in vielen Anwendungsfällen auf,
zum Beispiel in sozialen Netzwerken, Computernetzen und
Straßennetzwerken. Sie weisen oft spezielle Struktur auf, die
insbesondere weder gänzlich zufällig noch schlimmstmöglich ist. Es ist
wichtig, diese Struktur zu analysieren und verstehen, da sie uns viel zu
Entstehung und Funktion eines Netzwerks sagen kann. Ebenso kann solche
Struktur sehr nützlich sein, um schnellere Algorithmen auf diesen
Netzwerken zu ermöglichen, als es im Allgemeinen zu erwarten ist. Wir
interessieren uns hier für die Eignung bekannter Graphenparameter wie
Baumweite (treewidth) und Baumtiefe (treedepth), um die Struktur von
Netzwerken zu quantifizieren.
In diesem Semesterprojekt sollen
Heuristiken für drei Graphenparameter entwickelt werden. Des weiteren
sollen diese Heuristiken auf verschiedenen Graphen (soziale, Computer-
und Straßennetze) getestet und verglichen werden. Zu jedem Parameter
sollen zunächst je zwei Teams mit je zwei TeilnehmerInnen arbeiten,
wobei die Ergebnisse zum gleichen Parameter später zusammengeführt
werden sollen. Zu diesem Zweck, und zum Vergleich zwischen den
Parametern, sollen zu Beginn ein einheitliches Datenformat und ein
einheitlicher Programmaufbau festgelegt werden. Ebenso gilt es zu Beginn
gemeinsam die Definitionen der Parameter zu verstehen und geeignete
Daten zu beschaffen.
- Kursverantwortliche/r: Falko Hegerfeld