Ford-Fulkerson method
Residual networks
Intuitively, given a flow network $G$ and a flow $f$ , the residual network $G_f$ consists
of edges with capacities that represent how we can change the flow on edges of G.
Augmenting paths
Given a flow network $G=(V,E)$ and a flow $f$ , an augmenting path p is a
simple path from s to t in the residual network $G_f$.
Cuts of flow networks
A cut $(S,T)$ of flow network $G=(V,E)$ is a partition of $V$ into $S$ and
$T = V - S$ such that $s \in S$ and $t \in T$ .
basic Ford-Fulkerson algorithm
The Edmonds-Karp algorithm
We can improve the bound on FORD-FULKERSON by finding the augmenting
path p in line 3 with a breadth-first search. That is, we choose the augmenting
path as a shortest path from s to t in the residual network, where each edge has
unit distance (weight).
Running Time: $O(VE^2)$
Maximum bipartite matching
Thus, given a bipartite undirected graph $G$, we can find a maximum matching by
creating the flow network $G’$, running the Ford-Fulkerson method, and directly obtaining
a maximum matching $M$ from the integer-valued maximum flow $f$ found. Since anymatching in a bipartite graph has cardinality at most $min(L,R) = O(V)$, the value of the maximum flow in $G’$ is $O(V)$. We can therefore find a maximum matching in a bipartite graph in time $O(VE’) = O(VE)$
Push-relabel algorithms
The push operation
The relabel operation
The generic algorithm
The relabel-to-front algorithm
Discharging an overflowing vertex
The relabel-to-front algorithm
