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 Fluss an Waren von einer ausgezeichneten Quelle zu einer ausgzeichneten Senke zu erreichen (Max-Flow-Problem). Wir werden einige der besten Algorithmen für dieses Problem kennenlernen, insbesondere den Ende des 20. Jahrhunderts entdecketen Binary-Blocking-Flow-Algorithmus von Goldberg und Rao. Auch das Min-Cost-Max-Flow-Problem wird zur Sprache kommen.
Anmelderegeln
Diese Veranstaltung gehört zum Anmeldeset "Anmeldung gesperrt (global)".
