Network Flow III: scaling, Edmonds-Karp, applications, maximum bipartite matching, disjoint paths

Slides

Problems

· KT 7.3 Page 352: Choosing Good Augmenting Paths

· KT 7.5 Page 367: A First Application: The Bipartite Matching Problem

· KT 7.6: Page 373: Disjoint Paths in Directed and Undirected Graphs

Normal Fulkerson with depth first search time complexity

$$ O(E·f) $$

where E is the number of edges and f is the maximum flow

Edmond Karp with breath first search time complexity

$$ O(V·E^2) $$

where E is the number of edges and V is the number of vertices