Table of Contents

7.5 A First Application: The Bipartite Matching Problem


The Problem


Designing the Algorithm


Analyzing the Algorithm


=⇒ f(e) = 1 for each edge on one of these paths


Let's now consider the set M' of edges of the form (x,y) on which the flow value is 1:

Bounding the running time: The Ford-Fulkerson Algorithm can be implemented to find a maximum matching in a bipartite graph in O(mn) time.

Extensions: The Structure of Bipartite Graphs With No perfect Matching

When I was in class, I didn't have a chance to follow the lecture as much as I was supposed to. Because I had missed out on the foundations of this section, I couldn't find myself as I had a really bad week and couldn't review the slides. But reading this section helps me a lot and puts me a bit back on track.
I give this section an 8/10