Modification of Edmonds' maximum matching algorithm

Abstract

Edmonds d e veloped an efficient a lgorithm for finding in a given graph C a mat c hing of maximum cardinality. Thi s algorithm "s hrink s" part s of the graph C. Although helpful to th e intuitive und e rstanding of the theory, s hrinking is compl icated to im plem e nt on an e l<!'ctroni c co mput e r-Th e modificati o n present e d in thi s paper avoids s hrinking_ It e mploys in s tead a treelik e arrangement of alt e rnating path s. Th e possibili t y of s uc h an arrangement is also of th eo re ti ca l int e res t , and it s proof form s th e main part of th e paper-