Concepedia

An O(v|v| c |E|) algoithm for finding maximum matching in general graphs

1980 · 823 citations · 5 references

TL;DR

The paper proposes an O(√|V|·|E|) algorithm for maximum matching in general graphs, introducing a novel blossom‑handling technique that enables O(|E|) work per phase. The algorithm proceeds in phases that grow breadth‑first search trees from unmatched vertices, find a maximal set of disjoint minimum‑length augmenting paths, and use a delayed‑shrink strategy with a special labeling procedure to handle blossoms efficiently, achieving O(|E|) per phase. By delaying blossom shrinking, the algorithm guarantees that the first augmenting path found in each phase is of minimum length.

Abstract

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.