Liebe Interessierte am Thema Wegeprobleme in Graphen,

Wegeprobleme sind ein zentrales Thema der Graphentheorie, die beispielsweise im Zusammenhang mit Verkehrsinformationssystemen, Tourenplanung, Routing und Design von Netzwerken und in vielen weiteren Anwendungen eine wichtige Rolle spielen.

Im SS 2006 wird (Stefan Lewandowski eine 2-stündige Vorlesung über Wegeprobleme zu halten. Sie soll Fr 9.45-11.15 im Raum 1.124 stattfinden. In dieser Vorlesung soll ein Überblick über "Kürzeste-Wege"-Probleme und deren Lösung gegeben werden. Dabei stehen die Korrektheitsbeweise der Algorithmen und der Einfluss der verwendeten Datenstrukturen auf die Laufzeit der Algorithmen im Mittelpunkt. Für jedes der betrachteten Probleme werden mehrere Ansätze vorgestellt und miteinander verglichen. Die Vorlesung soll folgende Gliederung haben:

Einführung Einführende Definitionen + Dijkstra
Verfahren zur Bestimmung            Ein Meta - Algorithmus, Anwendungsergebnisse: Desopo / Bellmann
kürzester Wege Potentialfunktionen / Dijkstra und A*
Skalierung
APSP Probleme Vergleich zu SSSP
Beidseite Verfahren und deren Bewertung
Kürzeste Wege in Graphen kürzeste Wege in Graphen mit Abbiegeverboten
mit verbotenen Strukturen kürzeste Wege in Graphen mit Wegeverboten
Beweis der Korrektheit
Weitere Verfahren zur Varianten mit Buckets (Dinic, Denardo/Fox, Ahuja et al.)
Bestimmung kürzester Wege Varianten mit Separatoren (Frederickson)
Der Ansatz von Ichita
Kürzeste Wege in hierarchischen Graphen     Algorithmen, Konstruktion und Eigenschaften
k-kürzeste Wege Der Algorithmus von Pollack
Der Algorithmus von Hoffman & Pavley
Der Algorithmus von Azevedo




Literatur:

A. Brandstädt Graphen und Algorithmen Teubner, 1994
Buchholz, Friedhelm: Hierarchische Graphen zur Wegesuche Dissertation, Institut für Informatik, Universität Stuttgart, 2000
Lewandowski, Stefan: Anwendung für Separatortheoreme auf planaren Graphen, Diplomarbeit Nr. 1508, Fakultät Informatik, Universität Stuttgart, 1997
Lewandowski, Stefan: Vereinheitlichte Darstellung von Techniken zur effizienten Kürzeste-Wege-Suche Dissertation, Fakultät Informatik, Universität Stuttgart, 2005
M. Mack: Untersuchung von effizienten Algorithmen zur Bestimmung der k-kürzesten Wege innerhalb von ÖPNV-Verkehrsnetzen Diplomarbeit Nr. 1374, Fakultät Informatik, Universität Stuttgart, 1996
Schmid, Wolfgang: Berechnung kürzester Wege in Straßennetzen mit Wegeverboten Dissertation, Fakultät Vermessungswesen, Universität Stuttgart, 2000
Turau, Volker Algorithmische Graphentheorie Addison-Wesley Deutschland, 1996