LEA
Fakultät für Informatik der Technischen Universität München
Lehrstuhl für Effiziente Algorithmen
Postadresse: 80290 München; Hausadresse: Arcisstr.21, 80333 München

Seminar: Dynamische Graphenalgorithmen

Auskünfte u. Anmeldung bei Jesper Larsson Träff
[Zusammenfassung] [Themenliste] [Termine] [Hinweise] [Auskünfte u. Anmeldung]

Zusammenfassung

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.


Die folgenden Themen stehen zur Auswahl: Themen mit Literaturangaben in Postscript

  1. Transitive Hülle für gerichtete Graphen
  2. Kürzeste Wege

Dynamische Datenstrukturen

  1. Dynamische Bäume
  2. Topologische Bäume
  3. Gewurzelte Bäume

Techniken

  1. Sparsification
  2. Transformation eines dekremental-dynamischen zu einem voll-dynamischen Algorithmus

Randomisierte Algorithmen

  1. Zusammenhang
  2. Zweifachzusammenhang

Dynamische Algorithmen für planare Graphen

  1. Aufspannende Wälder
  2. Planarität

Deterministische Algorithmen mit polylogarithmischer Laufzeit

  1. Zusammenhang und aufspannende Wälder

Termine


Hinweise zur Gestaltung der Vorträge

* 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.)

Auskünfte und Anmeldung

Weitere Auskünfte und Anmeldungen bei Jesper Larsson Träff.


Martin Raab, Last modified: Fri Feb 27 11:08:41 MEZ 1998