Chapter 12: Network Flow and Matching. 25 sections.
25 items
You need to model the movement of resources through a constrained system.
Suppose you have already constructed a valid flow in a network.
Given a flow network with capacities on every edge, determine the maximum amount of flow that can be sent from the source to the sink.
The Ford-Fulkerson method provides a simple framework for computing maximum flow, but its performance depends heavily on the choice of augmenting paths.
Edmonds-Karp guarantees polynomial running time, but it still performs only one augmentation per BFS search.
The algorithms developed so far share a common strategy.
Maximum flow asks how much can be sent from a source to a sink.
A maximum-flow algorithm returns a number.
Suppose you have a set of workers and a set of tasks.
You need to find a maximum matching in a bipartite graph.
In maximum bipartite matching, every assignment has the same value.
You need to solve an assignment problem exactly.
Traditional maximum-flow algorithms answer a single question: > How much flow can be sent from the source to the sink?
So far, flow networks have had a source and a sink.
A normal flow edge has only an upper capacity: ```text 0 ≤ f(u, v) ≤ c(u, v) ```
Standard flow networks place capacity constraints on edges.
Suppose you are designing a communication network between two data centers.
Edge-disjoint paths are allowed to share vertices.
You have a set of possible projects.
Suppose you have an image and want to separate the foreground from the background.
Scheduling problems often look different from flow problems.
Flow algorithms are easy to implement incorrectly because their state changes over time.
Flow algorithms solve the same abstract problem, but their running times differ sharply.
Flow implementations are compact, but bugs are easy to hide.
Many optimization problems appear completely different on the surface.