8 Flüsse in Netzwerken
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 ...
Get Algorithmische Graphentheorie, 5th Edition now with the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.
