Seminar Dynamische Graphenalgorithmen, WS 00/01
Dynamische Graphenalgorithmen

Veranstaltung: Seminar, WS 00/01
Professur: Komplexität und Algorithmen
Dozent: Prof. Dr. Torben Hagerup
Zeit und Ort: Mi 12-14 Uhr, SR 11
Vorbesprechung: Di 27.6.00, 18 Uhr c.t., in SR 11.
Themen werden nur gegen Vorlage des Vordiploms ausgegeben.
Studienkredit: DPO83: T2
DPO90: T2
DPO97: T3
Studienabschnitt: Hauptstudium
Scheinerwerb: Bei erfolgreichem Vortrag, angenommener schriftlicher Ausarbeitung und aktiver Teilnahme
Voraussetzungen: Vordiplom
Inhalt: Graphen und Graphalgorithmen spielen in vielen Bereichen eine wichtige Rolle und sind schon aus den Grundvorlesungen bekannt. Die traditionell betrachtete Situation ist, dass ein Graph vorliegt und ein Algorithmus aufgerufen wird, um eine Frage über den Graphen zu beantworten, z.B. ob der Graph stark zusammenhängend ist. In manchen Anwendungen ist der Graph aber nicht statisch, sondern dynamisch, ändert sich somit im Laufe der Zeit. Wenn der Graph außerdem sehr groß ist (man denke z.B. an das World-Wide Web oder an Straßennetze), möchte man die Berechnung nicht nach jeder kleinen Änderung neu anwerfen müssen. Im Seminar werden wir uns eingehend mit Techniken beschäftigen, die es in einigen Fällen erlauben, Graphen effizient unter Folgen von Anfragen (z.B. `Gibt es einen Pfad von u nach v?') und Updates (z.B. die Einfügung einer neuen Kante) zu verwalten.
Vortragsthemen