An O{VTVT· IE I) Algorithm. for Finding lIaDmum Matching in General Graphs
Silvio Micali · 1980
In this paper we present..an O(JiVi.IEI) algo rithm for finding a maximum matching in general graphs. This algorithm works in 'phases'. In each phase a maximal set of disjoint minimum len gth augmenting paths is found, and the existing matching is increased along these paths. Our contribution consists in deVising a spe cial way of handling blossoms, which enables an O(lEI) implementation of a phase. In each phase, the algorithm grows Breadth First Search trees at all unmatched vertices. When it detects the pres ence of a blossom, it does not 'shrink' the blossom immediately. Instead, it delays the shrinking in such a way that the first augmenting path found is of minimum length. Furthermore, it achieves the effect of shrinking a blossom by a special labeling procedure which enables it to fin~ an augmenting path through a blossom quickly.