### 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=\left(U,V,E\right)$ where $U=\left\{{u}_{1},{u}_{2},\cdots ,{u}_{n}\right\}$ and $V=\left\{{v}_{1},{v}_{2},\cdots ,{v}_{n}\right\}$, Glover [Glover67] showed how to efficiently compute a maximum matching in such a graph:

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