1980/10/01 by Silvio Micali, Vijay V. Vazirani · 6 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Data Management and Algorithms #Graph Theory and Algorithms #Disjoint sets #Combinatorics #Matching (statistics) #Path (computing) #Set (abstract data type) #Mathematics #Computer science #Algorithm #Phase (matter) #Path length #Discrete mathematics #Physics
paper · doi:10.1109/sfcs.1980.12
openalex publication_date 1980/10/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/29
In this paper we present an 0(√|V|·|E|) algorithm for finding a maximum matching in general graphs. This algorithm works in 'phases'. In each phase a maximal set of disjoint minimum length augmenting paths is found, and the existing matching is increased along these paths. Our contribution consists in devising a special way of handling blossoms, which enables an O(|E|) implementation of a phase. In each phase, the algorithm grows Breadth First Search trees at all unmatched vertices. When it detects the presence 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 find an augmenting path through a blossom quickly.