Vorlesung Flüsse in Netzwerken, WS 99/00
Flüsse in Netzwerken

Veranstaltung: Vorlesung, WS 99/00
Professur: Komplexität und Algorithmen
Dozent: Prof. Dr. Torben Hagerup
Zeit und Ort: Mi,Do 12-14 Uhr, Magnus Hörsaal
Übungen: Do 14-16 Uhr, Magnus Hörsaal
Studienabschnitt: Hauptstudium
Scheinerwerb: Bei erfolgreicher Teilnahme an den Übungen
Voraussetzungen: Vordiplom, Interesse an algorithmischen Fragen
Inhalt: Die Vorlesung behandelt Flüsse in Netzwerken, Algorithmen zu ihrer Berechnung sowie Anwendungen von Flüssen bei der Modellierung und Lösung anderer algorithmischer Probleme.

Ein Netzwerk kann man sich als ein System von "Rohrleitungen" vorstellen, die eine bestimmte "Ware" transportieren können. Jedes Rohr hat eine Kapazität, die angibt, wieviel Ware pro Zeiteinheit durch das Rohr fließen kann; hierbei entstehen eventuell zusätzlich Kosten, die von dem Rohr abhängen.

Bei einem vorliegenden Netzwerk kann man sich eine Fülle algorithmischer Fragen stellen. Zentral für uns wird das Problem sein, einen möglichst großen Fluß an Waren von einer ausgezeichneten Quelle zu einer ausgezeichneten Senke zu erreichen (Max-Flow-Problem). Wir werden einige der besten Algorithmen für dieses Problem kennenlernen, insbesondere den erst vor zwei Jahren entdeckten Binary-Blocking-Flow-Algorithmus von Goldberg und Rao. Auch das Min-Cost-Flow-Problem wird zur Sprache kommen.

Literatur: R.K. Ahuja, T.L. Magnanti and J.B. Orlin, Network Flows, Prentice-Hall, Englewood Cliffs, NJ, 1993.