ABSTRACT
In this chapter we discuss algorithms for constructing a maximum matching (i.e., a matching with the largest cardinality) in a graph and some related problems. We begin with Berge’s alternating chain theorem which states that a matching M is maximum if and only if there is no alternating path between any two unsaturated vertices relative to M . This theorem is the basis of most maximum matching algorithms. We first discuss Edmonds’ approach for constructing a maximum matching in general graphs followed by Gabow’s O(n3) implementation of Edmonds’ approach. We then discuss algorithms for constructing maximum matchings in bipartite graphs. Specifically, we discuss a result due to Hopcroft and Karp which provides a basis for evaluating the complexity of maximum matching algorithms. We conclude with a discussion of four related problems: perfect matchings in bipartite graphs, Kuhn-Munkres’ algorithm for the optimum assignment problem, the timetable scheduling problem, and the Chinese Postman problem.
