|
|
|
|
|
Die Fragen, die in den klassischen Graphenalgorithmen betrachtet werden, entsprechen nicht immer der konkreten Anwendungssituation. Bei den üblicherweise studierten statischen Graphenproblemen ist eine Aufgabe (z.B. Berechnung der Zusammenhangskomponenten, Bestimmung eines minimal aufspannenden Waldes) auf einem durch die Eingabe fest vorgegebenen Graphen zu lösen.
Bei einem dynamischen Graphenproblem verändert sich der Graph - Kanten und Knoten können eingefügt oder gelöscht werden, und die Gewichte können sich ändern. Die Aufgabe besteht nun darin, das Problem für den veränderten Graphen zu lösen, ohne die Lösung nach jeder Veränderung vollkommen neu berechnen zu müssen. Die gerade erwähnten diskreten Änderungen an einem Graphen tauchen in vielen Anwendungsgebieten auf (Computernetzwerke, Computergrafik, VLSI-Design), und dynamische Graphenalgorithmen haben sich in den letzten Jahren zu einem sehr aktiven Forschungsgebiet entwickelt.
Im Seminar werden wir häufig vorkommende dynamische Probleme (transitive Hülle, Zusammenhang, minimale aufspannende Bäume), wichtige dynamische Datenstrukturen (dynamische Bäume) und allgemeine Techniken wie Sparsification und die Transformation eines partiell dynamischen Algorithmus zu einem voll dynamischen Algorithmus kennenlernen.
Einen guten Überblick über das Gebiet der dynamischem Graphenalgorithmen findet man in "Dynamic Graph Algorithms" von David Eppstein, Zvi Galil, Giuseppe F. Italiano.
|
Merkblatt zur Gestaltung eines Seminarvortrags. (Die Tips auf diesem Merkblatt sind keine offiziellen Anforderungen oder Bewertungskriterien der TU München, sondern aus der Praxis eines Seminarleiters heraus entstandene Ratschläge.) |
Weitere Auskünfte und Anmeldungen bei Jesper Larsson Träff.