image

KAPITEL8

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, 4th Edition now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.