Matchings and Assignments
Laurence A. Wolsey · 2020
Using alternating and augmenting paths, an algorithm for maximum cardinality matching in a bipartite graph is presented. This is then used as a subroutine in an algorithm to find a maximum weight matching in a bipartite graph (equivalently known as the assignment problem). Finally some fundamental results for the general (non-bipartite case) are presented without proof.