Premium
Maximum matchings in bipartite graphs via strong spanning trees
Author(s) -
Balinski M. L.,
Gonzalez J.
Publication year - 1991
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.3230210203
Subject(s) - bipartite graph , combinatorics , spanning tree , mathematics , matching (statistics) , characterization (materials science) , minimum spanning tree , discrete mathematics , graph , statistics , materials science , nanotechnology
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.