Forgetting Alternation and BlossomsResearch Paper
A maximum cardinality matching of a general graph can be found by repeatedly augmenting the current matching along a maximal set of vertex-disjoint shortest augmenting paths. Hopcroft and Karp showed that such phases suffice, so the whole difficulty is to compute one maximal set of disjoint shortest augmenting paths in nearly linear time. In…