Bipartite Matching
Unit-capacity network from a source through left and right to a sink. Each augmenting path is an alternating path.
Maximum Flow: Bipartite matching by augmenting paths
Augmenting path L1 > R1: L1 is free and so is R1, a direct match.
Cost
- Best
- O(E)
- Average
- O(V * E)
- Worst
- O(V * E)
- Space
- O(V + E)
Hopcroft-Karp achieves O(E sqrt(V)).
Before this
Taught by the same lesson
Maximum Flow covers these too, in the same run.