7.3. Bipartite Matching via Network Flows

In this section, we discuss that the maximum-cardinality matching problem, the maximum-weight matching problem, and the minimum-weight perfect matching problem in bipartite graphs can be solved using network flow algorithms. The maximum-cardinality matching problem can be expressed as a maximum flow problem. The maximum-weight matching problem and the minimum-weight perfect matching problem can be expressed as minimum-cost flow problems.