Chapter 7.5: A First Application: The Bipartite Matching Problem

A bipartite graph is an undirected graph whose node set can be partitioned as V = X U Y, with the property that every edge e in E has one end in X and the other end in Y. A matching M in G is a subset of the edges M including E such that each node appears in at most one edge in M. The Bipartite Matching Problem is that of finding a matching in G of largest possible size.

Designing the Algorithm

Beginning with the graph G, we construct a flow network G'. First we direct all edges in G from X to Y, then we add nodes s and t and give each edge in G' a capacity of 1. We now compute a maximum s-t flow in this network G'. The value of this maximum is equal to the size of the maximum matching in G. Bam.

Runtime: O(mn) —> same as Ford-Fulkerson Algorithm. This section was pretty self explanatory. 9/10.