Maximum matchings in bipartite graphs via strong spanning trees
- 1 March 1991
- Vol. 21 (2) , 165-179
- https://doi.org/10.1002/net.3230210203
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.Keywords
This publication has 10 references indexed in Scilit:
- A competitive (dual) simplex method for the assignment problemMathematical Programming, 1986
- Efficient dual simplex algorithms for the assignment problemMathematical Programming, 1985
- Network Flow and Testing Graph ConnectivitySIAM Journal on Computing, 1975
- An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite GraphsSIAM Journal on Computing, 1973
- Networks and Basic SolutionsOperations Research, 1966
- Flows in NetworksPublished by Walter de Gruyter GmbH ,1963
- An algorithm for a minimum cover of a graphProceedings of the American Mathematical Society, 1959
- TWO THEOREMS IN GRAPH THEORYProceedings of the National Academy of Sciences, 1957
- An Algorithm for Distinct RepresentativesThe American Mathematical Monthly, 1956
- The Hungarian method for the assignment problemNaval Research Logistics Quarterly, 1955