Algorithmische Graphentheorie

Dieses Kapitel behandelt Verfahren zur Bestimmung von maximalen Flüssen in Netzwerken mit oberen Kapazitätsbeschränkungen. Zunächst werden die grundlegenden Resultate von Ford und Fulkerson bewiesen. Danach werden zwei Algorithmen zur Bestimmung von maximalen Flüssen vorgestellt. Der erste basiert auf Erweiterungswegen minimaler Länge, der zweite verwendet die Technik der blockierenden Flüsse. Für den Fall, dass die Kapazitäten 0 oder 1 sind, werden schärfere Komplexitätsabschätzungen angegeben. Im letzten Abschnitt werden kostenminimale Flüsse betrachtet. Anwendungen von Netzwerkalgorithmen werden im nächsten Kapitel behandelt.

Kapitelübersicht

1. Einleitung
2. Einführung
3. Bäume
4. Suchverfahren in Graphen
5. Entwurfsmethoden für die algorithmische Graphentheorie
6. Färbung von Graphen
7. Perfekte Graphen
8. Flüsse in Netzwerken
   1. Einleitung
   2. Schnitte und Erweiterungswege
   3. Der Satz von Ford-Fulkerson
   4. Bestimmung von Erweiterungswegen
   5. Der Algorithmus von Dinic
   6. 0-1-Netzwerke
   7. Kostenminimale Flüsse
   8. Literatur
   9. Aufgaben
9. Anwendungen von Netzwerkalgorithmen
10. Kürzeste Wege
11. Approximative Algorithmen