03 Maximum Flow

Algorithms and Data Structures 2
Maximum Flow
Kathrin Hanauer Gramoz Goranci
Theory and Application of Algorithms (TAA)

Faculty of Computer Science
Winter Semester 2023
Kathrin Hanauer, Gramoz Goranci Algorithms and Data Structures 2: Maximum Flow 1
Acknowledgements
Material based on slides by Monika Henzinger, Christian Schulz
Original slides by Kurt Mehlhorn, Peter Sanders, and Rob van Stee
Definitions: Flow Network
▶ Flow Network: directed, weighted, simple graph G = (V , E , c, s, t) with
distinguished source node s and sink node t
simple graph: no pairs of anti-parallel edges, no loops
▶ We use n := |V | and m := |E |
▶ Weight c(e) of an edge e is called the capacity of e , c(e) ≥ 0
▶ Generalization of c to V × V : c(u, v ) = 0 if (u, v ) ̸∈ E
10
u v
12
10
4
s 4 t
10 8
w x
4
Definitions: Flow
A flow is a function f : V × V → R that satisfies
▶ ∀(u, v ) ∈ V × V : 0 ≤ f (u, v ) ≤ c(u, v ) (capacity constraints)
▶ ∀v ∈ V \ {s, t} :
P P
f (u, v ) = f (v , u) (flow conservation)
u∈V u∈V
The value |f | of a flow f is the flow leaving s minus the flow entering it:
P P
|f | = f (s, v ) − f (v , s) ≥ 0.
v ∈V v ∈V
Maximum flow: a flow of maximum value

8/10
u v
0 12
/1 /1
10 2
2/
4
s 4/
4 t
8/ 8
10 6/
w x |f | = 10 + 8 = 18
4/4
Definitions: s-t Cut
▶ s -t cut: partition (S, T ) of V such that s ∈ S and t ∈ T
▶ Let E (S, T ) = {(u, v ) ∈ E | u ∈ S ∧ v ∈ T } = E ∩ (S × T )
▶ The capacity of a cut is c(S, T ) =
P P
c(u, v ) = c(e)
u∈S,v ∈T e∈E (S,T )
Minimum s -t cut: a cut of minimum capacity
10
u v
12
10
4
s t
S
4
10 8
w x T
4
c({s, w } , {u, v , x , t}) = 10 + 4 + 4 = 18

Applications
▶ Oil pipes
▶ Traffic flows on highways
▶ Computer Vision
• Image Smoothing
• Image Segmentation
• Stereo Processing
• Multiview Reconstruction
• Panoramas
• ...
▶ Bipartite Matching
▶ Network Reliability
▶ Scheduling
▶ Matrix Rounding
▶ ...
A (Too) Greedy Algorithm
0 Set f (e) = 0 ∀e ∈ E .
1 Try to find a path P = s ; t such that each edge e has

P P spare capacity, i. e. , f (e) < c(e).
3 Terminate. 2 Augment the flow along P by the minimum spare ca-

pacity.
8 10/10
u v
2 12
10 /1
0/ 2
0/
1
4
s t
4
4
2/
6/ 8
1 4/
8 0 18
w x 6
4/4 |f | = 16
Residual Graph
Given a network G = (V , E , c, s, t) and a flow f , the residual network is a graph

Gf = (V , Ef , cf , s, t), where reverse edge (v , u) of e = (u, v )
▶ Ef = {e | e ∈ E ∧ f (e) < c(e)} ∪ {e rev | e ∈ E ∧ f (e) > 0},
(
c(e) − f (e), if e ∈ E (remaining capacity)
▶ cf (e) = (residual capacity)
rev rev
f (e ), if e ∈ E (cancellable flow)
10/10
u v u v
12 10
10 /1 4
0/ 2
0/
1
12
4
10
s t s t
4 4
2
4
2/
6/ 8 2
10 4/ 6 4
w x w x
4/4 4
flow network G with flow f corresponding residual graph Gf
Augmenting Paths
An augmenting path is a simple path P = s ; t in Gf .
The residual capacity or bottleneck capacity of an augmenting path P is

cf (P) = min cf (e).
e on P
A bottleneck edge is an edge on P ( with cf (e) = cf (P).
cf (P), if (u, v ) is on P,
Let fP : V × V → R with fP (u, v ) =
0, otherwise.
Then, fP is a flow in Gf and |fP | = cf (P) > 0.
u v
10
4
12
10
s t
4 4
2
6 2
4
w x
4
Augmenting Paths
Lemma
If f is a flow in a network G = (V , E , c, s, t) and P is an augmenting path in Gf , then
f + fP : V × V → R with (
f (u, v ) + fP (u, v ) − fP (v , u), if (u, v ) ∈ E
(f + fP )(u, v ) =
0, else.
is a flow in G with |f + fP | = |f | + |fP |.
Proof.
Capacity constraints: ∀(u, v ) ∈ V × V : 0 ≤ (f + fP )(u, v ) ≤ c(u, v ).
If (u, v ) ̸∈ E , then (f + fP )(u, v ) = 0. Else,
≤cf (v ,u)=f (u,v )
z }| {
(f + fP )(u, v ) = f (u, v ) + fP (u, v ) − fP (v , u) ≥ fP (u, v ) ≥ 0.
(f + fP )(u, v ) = f (u, v ) + fP (u, v ) − fP (v , u) ≤ f (u, v ) + fP (u, v ) ≤ c(u, v ).
| {z }
≤cf (u,v )=c(u,v )−f (u,v )
Augmenting Paths
Proof (Cont.)
P P
Flow conservation: ∀u ∈ V \ {s, t} : (f + fP )(u, v ) = (f + fP )(v , u).
v ∈V v ∈V
P P
(f + fP )(u, v ) = f (u, v ) + fP (u, v ) − fP (v , u)
v ∈V v ∈V
P P P
= f (u, v ) + fP (u, v ) − fP (v , u)
v ∈V
P v ∈V
P v ∈V
P
= f (v , u) + fP (v , u) − fP (u, v )
v ∈V
P v ∈V v ∈V P
= f (v , u) + fP (v , u) − fP (u, v ) = (f + fP )(v , u).
v ∈V v ∈V
Value of flow f + fP :
P P
|f + fP | = (f + fP )(s, v ) − (f + fP )(v , s)
v ∈V
P v ∈V P
= f (s, v ) + fP (s, v ) − fP (v , s) − f (v , s) + fP (v , s) − fP (s, v )
+
v ∈N (s)
P P v ∈N − (s)
= f (s, v ) − f (v , s)
v ∈N + (s) v ∈N − (s)
P P P P
+ fP (s, v ) + fP (s, v ) − fP (v , s) − fP (v , s)
+
v ∈N − (s) v ∈N + (s) v ∈N − (s)
Pv ∈N (s)
P
= f (s, v ) − f (v , s) + fP (s, v ) − fP (v , s) = |f | + |fP |
v ∈V v ∈V
N + (s), N − (s) : out-/in-neighbors of s. Note that N + (s) ∩ N − (s) = ∅ as G simple.

Ford-Fulkerson Algorithm
Augment(Gf , P) FordFulkerson(G)
cf (P) ← mine on P cf (e) for all e ∈ E do f (e) ← 0
for all e on P do construct Gf
if e ∈ E then while ∃P = s ; t in Gf do
f (e) ← f (e) + cf (P) Augment(Gf , P)
else f (e rev ) ← f (e rev ) − cf (P) update Gf
u v
10
4
12
10
s t
4 4
2
6 2
4
w x
4 |f | = 16
Ford-Fulkerson Algorithm
Augment(Gf , P) FordFulkerson(G)
cf (P) ← mine on P cf (e) for all e ∈ E do f (e) ← 0
for all e on P do construct Gf
if e ∈ E then while ∃P = s ; t in Gf do
f (e) ← f (e) + cf (P) Augment(Gf , P)
else f (e rev ) ← f (e rev ) − cf (P) update Gf
2
u v
8
2
12
10
s 2 t
2 2
8 4
6
w x
4 |f | = 18
Flows and Cuts
Lemma (Flow Value)

If f is a flow in a network G = (V , E , c, s, t) and (S, T ) an s-t cut, then f ’s value equals the
net flow across the cut, i. e. ,
P P
|f | = f (u, v ) − f (v , u)
u∈S,v ∈T u∈S,v ∈T
P P
Proof. |f | = f (s, v ) − f (v , s)
v ∈V v ∈V
P P P P
= f (s, v ) − f (v , s) + f (u, v ) − f (v , u)
v ∈V v ∈V u∈S\{s} v ∈V
| {z }
=0 (flow conservation)
P P P P
= f (u, v ) − f (v , u)
u∈S v ∈V u∈S v ∈V
PP P P PP P P
= f (u, v ) + f (u, v ) − f (v , u) − f (v , u)
u∈S v ∈S u∈S v ∈T u∈S v ∈S u∈S v ∈T
P P P P
= f (u, v ) − f (v , u).
u∈S v ∈T u∈S v ∈T
Weak Duality
Theorem (Weak Duality)

If f is a flow in a network G = (V , E , c, s, t) and (S, T ) an s-t cut, then
|f | ≤ c(S, T ).
Proof.
By the Flow Value lemma,
X X X X
|f | = f (u, v ) − f (v , u) ≤ f (u, v ) ≤ c(u, v ) = c(S, T ).
u∈S,v ∈T u∈S,v ∈T u∈S,v ∈T u∈S,v ∈T
Corollary (Weak Duality)

Let f be a flow in a network G = (V , E , c, s, t) and (S, T ) an s-t cut. If |f | = c(S, T ), then f
is a maximum flow and (S, T ) is a minimum cut.
Proof.
Let f ′ be any flow and let (S ′ , T ′ ) be any s-t-cut. By the Weak Duality theorem,
|f ′ | ≤ c(S, T ) = |f | ≤ c(S ′ , T ′ ).
Max-Flow Min-Cut Theorem
Theorem (Max-Flow Min-Cut)

If f is a flow in a network G = (V , E , c, s, t), then the following conditions are equivalent:
(i) There is an s-t cut (S, T ) with c(S, T ) = |f |.
(ii) f is a maximum flow in G.
(iii) Gf contains no augmenting paths.
Proof.
(i) ⇒ (ii) Follows by the Weak Duality corollary.
(ii) ⇒ (iii) Suppose Gf contains an augmenting path P. Then, |f | can be increased by |fP | > 0, so f is
not a maximum flow, a contradiction.
(iii) ⇒ (i) Let S be the set of all vertices reachable from s in Gf and T = V \ S. Then, s ∈ S, t ∈ T ,
and (S, T ) is an s-t-cut. For any (u, v ) ∈ S × T , cf (u, v ) = 0, i.e., (1) if e = (u, v ) ∈ E , then
f (e) = c(e) and (2) if e = (v , u) ∈ E , then f (e) = 0. By the Flow Value lemma,
P P P
|f | = f (u, v ) − f (v , u) = c(u, v ) − 0 = c(S, T ).
u∈S,v ∈T u∈S,v ∈T u∈S,v ∈T
| {z } | {z }
apply (1) apply (2)
Strong Duality
Theorem (Strong Duality)

Let f ∗ be a maximum s-t flow and let (S ∗ , T ∗ ) be a minimum s-t cut. Then, |f ∗ | = c(S ∗ , T ∗ ).
Proof.
We show the claim in two steps:
“≤”: By the Weak Duality theorem, |f | ≤ c(S, T ) for any s-t flow f and any s-t cut (S, T ).
Hence, it holds in particular that |f ∗ | ≤ c(S ∗ , T ∗ ).
“≥”: By the Max-Flow Min-Cut theorem, there is an s-t cut (S, T ) with c(S, T ) = |f ∗ |.
Hence, |f ∗ | = c(S, T ) ≥ c(S ∗ , T ∗ ), as (S ∗ , T ∗ ) is minimum.
Ford-Fulkerson Algorithm: Correctness
▶ If the Ford-Fulkerson algorithm terminates, the residual graph contains no

augmenting path.
▶ By the Max-Flow Min-Cut theorem, the computed flow is maximum.
Does the algorithm always terminate?
A bad example . . .
u 10
0 0 00
000 00
10 0
s 10 1 t
0
00 00
00 00
0 10
v
...
Ford-Fulkerson Algorithm: Correctness
▶ If the Ford-Fulkerson algorithm terminates, the residual graph contains no

augmenting path.
▶ By the Max-Flow Min-Cut theorem, the computed flow is maximum.
Does the algorithm always terminate?
A bad example . . .
u 10
9 00
999 00
99 0
1
s 10 1 t
0 9
00
0 9 99
0 99
1
v
...
Ford-Fulkerson Algorithm: Termination
Theorem
Let G = (V , E , c, s, t) be a flow network and let |f ∗ | be the value of a maximum flow. If all
capacities in G are integral, the Ford-Fulkerson algorithm terminates in O(m · |f ∗ |) time.
Proof.
▶ Finding an s-t path in Gf , augmenting FordFulkerson(G)
for all e ∈ E do f (e) ← 0
the flow on it, and updating Gf takes construct Gf
O(n + |Ef |) = O(|Ef |) = O(m) time. while ∃P = s ; t in Gf do
▶ Each iteration of the while loop Augment(Gf , P)
update Gf
takes O(m) time.
▶ In each iteration, the flow increases by at least one unit.
⇒ There are at most |f ∗ | iterations.
▶ The initialization takes O(m) time.
⇒ The algorithm runs in O(m · |f ∗ |) time.
Note: There are networks where the Ford-Fulkerson algorithm may fail to terminate.
Ford-Fulkerson Algorithm: Termination
There are networks where the Ford-Fulkerson algorithm may fail to terminate:
√
Let M ≥ 4 and r = 5−12 ≈ 0.618. (Note: 1 − r = r 2 )
Consider the network on the right along with the following augmenting paths:
u
P0 = ⟨s, w , v , t⟩ |f | = 1 r M
P1 = ⟨s, u, v , w , x , t⟩ |f | = 1 + r M
v
P2 = ⟨s, w , v , u, t⟩ |f | = 1 + 2r
P3 = P1 = ⟨s, u, v , w , x , t⟩ |f | = 1 + 2r + r2 s M
M 1 t
P4 = ⟨s, x , w , v , t⟩ |f | = 1 + 2r + 2r 2 w
P5 = P1 = ⟨s, u, v , w , x , t⟩ |f | = 1 + 2r + 2r 2 + r 3 M
P6 = P2 = ⟨s, w , v , u, t⟩ |f | = 1 + 2r + 2r 2 + 2r 3 1 M
x
P0 (P1 , P2 , P1 , P4 )∗ is an infinite sequence of augmenting paths.

∞
r i = 1 + 2r < 5, whereas the maximum flow is 2M + 1.
P
The flow value converges to 1 + 2
i=1
Uri Zwick. The smallest networks on which the Ford-Fulkerson maximum
flow procedure may fail to terminate. TCS 148(1), 1995, pp. 165–170.
Choosing Augmenting Paths
On a network with integral capacities and maximum edge capacity C , the
Ford-Fulkerson algorithm runs in time O(m · |f ∗ |) ⊆ O(m · n · C ).
Are there clever(er) ways to choose augmenting paths?

▶ Look for paths with large residual capacity ⇒ O(m2 · log C )
▶ Look for shortest paths (w. r. t. the number of edges)
Known as Edmonds-Karp algorithm.
⇒ O(m2 · n)
▶ Look for all shortest paths “at once”, before updating the flow and recomputing Gf ,
so-called “blocking flows” Dinitz algorithm
⇒ O(n2 · m)
Level Graph
▶ Let G = (V , E ) be a graph and s ∈ V .
▶ For each vertex v ∈ V , let l(v ) denote v ’s distance from s (the number of edges
on a shortest path s ; v ).
▶ The level graph G L = (V , E L ) of G is the subgraph of G that contains only the
edges E L = {(u, v ) ∈ E | l(u) + 1 = l(v )}.
▶ P = s ; v is a path in G L ⇔ P is a shortest path in G
▶ Can be computed via breadth-first search in O(n + m).
u v
s t
w x
Levels: l=0 l=1 l=2 l=3
Blocking Flows
Edmonds-Karp needs O(n · m) augmentations. Can we do better than that?
There are networks that require Θ(n · m) augmentations.
⇒ Try to speed up the augmentation process!
Let f be a flow in a network G = (V , E , c, s, t).

A blocking flow is a flow f ′ in Gf such that each path s ; t in GfL contains at least one
bottleneck edge.
4/4
u v
0 4/
/1 10
10
6/
s 2 6 t
4/
10 8 /1
0
4/9 10
w x
Blocking Flows
How to Find a Blocking Flow

0 Initialization: Construct the level graph GfL .
1 Advance: Starting from s, follow edges of GfL as in a depth-first search.
2 Augment: If reach t, augment flow along s ; t, remove bottleneck edges, and start again
from s.
3 Retreat: If get stuck at vertex v , remove v from GfL and go back to previous vertex.
4
u v
10
10
s t
8
10
10
9
w x
Blocking Flows

from s.
4
u v
10
10
s t
8
10
10
9
w x
Blocking Flows

from s.
u v
6 6
s t
10 8
10
9
w x
Blocking Flows

from s.
u v
6
s t
2
10 4
9
w x
Blocking Flows

from s.
u v
6
s t
2
6
5
w x
Blocking Flows

from s.
u v
6
s t
6
w
Blocking Flows

from s.
u v
6
s t
Dinitz Algorithm
BlockingFlow(Gf )
Dinitz(G) construct level graph GfL of Gf
for all e ∈ E do f (e) ← 0 P ← ⟨⟩; v ← s; blocking ← false
while !blocking do
construct Gf
if v = t then ▷ augment
while ∃s ; t in Gf do
Augment(Gf , P)
BlockingFlow(Gf )
remove bottleneck edges from GfL
update Gf
P ← ⟨⟩; v ← s
else if ∃(v , w ) ∈ EfL then ▷ advance
P ← P + (v , w ); v ← w
else ▷ retreat
computation of a blocking flow, if v = s then
including update of Gf blocking ← true
=
b else
remove v from GfL
“phase” remove last edge (u, v ) from P
v ←u
Dinitz Algorithm: Analysis
Lemma
The Dinitz algorithm uses at most O(n) phases.
Proof.
After each phase, the distance from s to t increases strictly. As the maximum distance is n − 1, there
can be at most O(n) phases.
Lemma
Each phase in the Dinitz algorithm takes at most O(nm) time.
Proof.
In each phase . . .
. . . the computation of GfL via BFS takes O(m) time,
. . . there are at most m augmentations (each augmenting path has at least one bottleneck edge,
which is then removed),
. . . there are at most n retreats,
. . . there are at most n advances before an augmentation or a retreat, i. e. , at most n · m advances in
total.
Hence, each phase can be implemented in O(n · m) time.
Dinitz Algorithm: Analysis
Theorem
The Dinitz algorithm computes a maximum flow in time O(n2 m).
Proof.
There are at most O(n) phases and each phase can be implemented in O(n · m) time. Hence, the
algorithm runs in O(n2 m) time.
Using dynamic trees, each phase can be implemented in O(m log n) time.
Theorem
The Dinitz algorithm with dynamic trees computes a maximum flow in time O(n · m log n).
Maximum Flow Algorithms
Year Method Running time By
1956 augmenting paths O(nmC ) Ford & Fulkerson
1969 shortest augmenting paths O(nm2 ) Edmonds & Karp
1970 blocking flows O(n2 m) Dinitz
1973 capacity scaling O(nm log C ) Dinitz
1974 blocking flows + preflow O(n3 ) Karzanov
1980 blocking flows O(nm log2 n) Galil & Naamad
1983 blocking flows + dynamic trees O(nm log n) Sleator & Tarjan
1986 push-relabel O(n3 ) Goldberg & Tarjan
2
push-relabel + dynamic trees O(nm log nm )
√
1989 highest-label push-relabel O(n2 m) Cheriyan & Maheshwari
2 √
1998 binary blocking flows O(min{n 3 , m} Goldberg & Rao
2
·m log nm log C )
2013 compact networks O(nm) Orlin
√
2014 interior-point methods Õ(m n log C ) Lee & Sidford
2016 electrical flows Õ(m10/7 C 1/7 ) Mądry
2022 min-ratio cycles O(m1+o(1) log C ) Chen, Kyng, Liu, Peng, Gutenberg, Sachdeva
n = |V |, m = |E |, C = maximum edge capacity (integral)
Note: This list is incomplete (by far)!
Maximum Bipartite Matching
A matching in an undirected graph G = (V , E ) is a

set M ⊆ E such that every vertex is the end vertex
of at most one edge in M .
An undirected graph G = (V , E ) is bipartite if its

vertex set can be partitioned such that no edge has
both end vertices in the same partition, i. e. ,
V = V1 ⊔ V2 and E ⊆ V1 × V2 .

Given: undirected, bipartite graph G = (V1 ⊔ V2 , E ⊆ V1 × V2 )
Wanted: a matching M of maximum cardinality
Maximum Bipartite Matching ⇒ Maximum Flow

Given: undirected, bipartite graph G = (V1 ⊔ V2 , E ⊆ V1 × V2 )
Construct a flow network G ′ from G as follows:
▶ Add a source vertex s and a sink vertex t.
▶ Add an edge from s to every vertex in V1 with capacity 1.
▶ Add an edge from every vertex in V2 to t with capacity 1.
▶ Direct all original edges from V1 to V2 and set their capacity to 1.
1
1 1
1
1
1 1
1
s 1 t
1 1
1
1 1
Theorem
An undirected, bipartite graph G = (V1 ⊔ V2 , E ⊆ V1 × V2 ) has a matching of cardinality k if
and only if the corresponding flow network G ′ has a flow of size k.
Proof: “⇒”.
▶ Let M be a matching in G with |M| = k.
▶ In G ′ , set f (s, u) = f (u, v ) = f (v , t) = 1 if {u, v } ∈ M and f (e) = 0 for all other edges.
▶ Then, f is a flow in G ′ and |f | = k.
1/1
0/1 1/
1
1/
0/
1
1
0/1 0/1
1/1
s 1/1 t
1/1 1
1/
1
1/
1/
1
0/1
Theorem
An undirected, bipartite graph G = (V1 ⊔ V2 , E ⊆ V1 × V2 ) has a matching of cardinality k if
and only if the corresponding flow network G ′ has a flow of size k.
Proof: “⇐”.
▶ Let f be a flow in G ′ with |f | = k.
▶ All capacities in G ′ are integral, so f is integral (in fact, f is 0-1).
▶ Let M = {{u, v } ∈ E | f (u, v ) = 1}. By construction, every vertex in G is the end vertex
of at most one edge in M, so M is a matching.
▶ Due to flow conservation, |f | = u∈V f (s, u) = u∈V ,v ∈V f (u, v ) = |M| = k.
P P
1 1 2
1/1
0/1 1/
1
1/
0/
1
1
0/1 0/1
1/1
s 1/1 t
1/1 1
1/
1
1/
1/
1
0/1
Algorithms:
Year Method Running time By
1956 augmenting paths O(nm) Ford & Fulkerson
√
1973 blocking flows O( nm) Hopcroft & Karp, Karzanov
2004 fast matrix multiplication O(n2.376 ) Mucha & Sankowski
2016 electrical flows Õ(m10/7 ) Mądry
n = |V |, m = |E |
Note: This list is very likely incomplete.
Real-world applications:
All kinds of assignment problems: agents & tasks, machines & jobs, hospital &
patients, kidney donors . . .
Subgraph isomorphism
Computer vision (e.g. following/recognizing objects between frames, after blurring, . . . )
...

03 Maximum Flow

Uploaded by

Copyright:

Available Formats

03 Maximum Flow

Uploaded by

Document Information

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

03 Maximum Flow

Uploaded by

Copyright:

Available Formats

Algorithms and Data Structures 2

Kathrin Hanauer Gramoz Goranci

Theory and Application of Algorithms (TAA)

Winter Semester 2023

Maximum flow: a flow of maximum value

c({s, w } , {u, v , x , t}) = 10 + 4 + 4 = 18

1 Try to find a path P = s ; t such that each edge e has

3 Terminate. 2 Augment the flow along P by the minimum spare ca-

Given a network G = (V , E , c, s, t) and a flow f , the residual network is a graph

flow network G with flow f corresponding residual graph Gf

An augmenting path is a simple path P = s ; t in Gf .

The residual capacity or bottleneck capacity of an augmenting path P is

N + (s), N − (s) : out-/in-neighbors of s. Note that N + (s) ∩ N − (s) = ∅ as G simple.

Lemma (Flow Value)

Theorem (Weak Duality)

Corollary (Weak Duality)

Theorem (Max-Flow Min-Cut)

Theorem (Strong Duality)

▶ If the Ford-Fulkerson algorithm terminates, the residual graph contains no

▶ If the Ford-Fulkerson algorithm terminates, the residual graph contains no

P0 (P1 , P2 , P1 , P4 )∗ is an infinite sequence of augmenting paths.

Are there clever(er) ways to choose augmenting paths?

Let f be a flow in a network G = (V , E , c, s, t).

How to Find a Blocking Flow

How to Find a Blocking Flow

How to Find a Blocking Flow

How to Find a Blocking Flow

How to Find a Blocking Flow

How to Find a Blocking Flow

How to Find a Blocking Flow

A matching in an undirected graph G = (V , E ) is a

An undirected graph G = (V , E ) is bipartite if its

Maximum Bipartite Matching

Maximum Bipartite Matching ⇒ Maximum Flow

You might also like