A perfect matching algorithm for sparse bipartite graphs (Q759771)

The algorithms for finding a perfect matching, if any, in a bipartite undirected graph G usually start with a matching (which may not be maximum) and construct, if it exists, a matching of greater cardinality by determining augmenting paths. This is generally obtained through an associated directed graph \(\bar G.\) The paper shows that those edges of \(\bar G\) which link vertices belonging to different strongly connected components should not be included in augmenting paths. An application to the block triangularization of very large, sparse, nonsingular matrices is given.