Alternative polynomial-time algorithm for Bipartite Matching

Sylvain Guillemot

If $G$ is a bipartite graph, Hall's theorem \cite{H35} gives a condition for the existence of a matching of $G$ covering one side of the bipartition. This theorem admits a well-kno…