CO250 Study Guide - Final Guide: Hungarian Algorithm, Bipartite Graph

• School: University of Waterloo
• Department: Combinatorics and Optimization
• Course: CO250
• Professor: Joseph Cheriyan

Document Summary

Minimum cost perfect matching in bipartite graphs hungarian algorithm. Here is a complete example of the algorithm to find a minimum cost perfect matching in bipartite. Graphs (i. e. algorithm 3. 3 in the textbook, page 128). For the following bipartite graph g with edge costs c (as shown in the gure), we will nd a perfect matching of minimum cost (if one exists). r q p. 0, 2 w 1 t 1 s 1 r q p. Observe that the set s := {p, q} is a de cient set in h, since nh (s) = {t}. S q s 1 p w t s. Observe that the set s := {p, q, r} is a de cient set in h, since nh (s) = {s, t}. However, s is not de cient in g since ng(s) = {s, t, w}.