Maximum matchings in bipartite graphs via strong spanning trees
Michel Balinski, J. Gonzalez · Networks · 1991
Abstract A new characterization of maximum matchings for bipartite graphs is presented. It is based on “strong spanning trees” and permits the development of a new algorithm that does not use the classical notion of augmenting paths and that runs in O (| V | | E |) time for bipartite graphs with | V | nodes and | E | edges.