3. Bipartite Matching Algorithms
Society for Industrial and Applied Mathematics eBooks · 2012
3.1 Bipartite matching In the introductory chapters it turned out that finding a maximum cardinality matching in a bipartite graph plays a crucial role for assignment problems. Therefore, we discuss in this chapter various efficient methods for finding maximum matchings in bipartite graphs. Let be a bipartite graph with vertex sets and and assume . The classical method uses simple labeling strategies for finding augmenting paths which finally lead to a maximum matching. This basic method has time complexity O(|U||E|).