Bipartite Matching (17)
Michael L. Littman
October 29th, 1998
MATCHING PROBLEM
Teaching Assignments
Example Semester
Bipartite Graphs
Matching
Max Matchings
Finding a Max Matching
MIN-CUT MAX-FLOW
Augmenting Path
Augmenting Path Facts
Algorithm
Cuts
Max-flow Min-cut Theorem
Proof of Max-flow Min-cut
FORD-FULKERSON METHOD
Review
Augmenting-Path Algorithm
Overall Running Time
GENERALIZATIONS
Network Flow
Linear Programming
Next:
MATCHING PROBLEM