3.7.34. Bipartite matching in convex bipartite graphs

Denotes that, for a given constraint, a bipartite matching algorithm using Glover's rule for constructing a maximum matching of a convex bipartite graph can be used. Given a convex bipartite graph G=(U,V,E) where U={u 1 ,u 2 ,⋯,u n } and V={v 1 ,v 2 ,⋯,v n }, Glover [Glover67] showed how to efficiently compute a maximum matching in such a graph:

  1. First start with the empty matching.

  2. Second for each vertex v j of V, (j=1,2,⋯,m), if v j has still a free neighbour in U, then add to the current matching the edge (u i ,v j ) for which u i is free and α i =max{j:(x i ,y j )∈E,y j ∈V} is as small as possible.