The blossom algorithm checks for the existence of an augmenting path by a tree search as in the bipartite case, but with special handling for
the odd-length cycles that can arise in the general case. Such a cycle is called
a blossom. The blossom can be shrunk and the search restarted recursively. If an
augmenting path in a shrunken graph is ever found,
it can be expanded up through the blossoms to yield an augmenting
path in the original; that alternating path can be used to augment the matching
by one edge. And if the recursive process runs into a state where there is no augmenting path, then there is none in the original
graph.
Cook, W. J.; Cunningham, W. H.; Pulleyblank, W. R.; and Schrijver, A. Combinatorial
Optimization. New York: Wiley, 1998.Edmonds, J. "Paths,
Trees, and Flowers." Canad. J. Math.17, 449-467, 1965.Gabow,
H N. and Tarjan, R E. "Faster Scaling Algorithms for General Graph
Matching Problems." J. ACM38, 815-853, 1991.Kolmogorov,
V. "Blossom V: A New Implementation of a Minimum Cost Perfect Matching Algorithm."
Mathematical Programming Comput.1, 43-67, 2009. Kusner, M. and Wagon,
S. "The Blossom Algorithm for Maximum Matching." http://demonstrations.wolfram.com/TheBlossomAlgorithmForMaximumMatching/.Micali,
S. and V.V. Vazirani, V. V. "An Algorithm for Finding Maximum Matching
in General Graphs." In Proc. 21st FOCS, pp. 17-27, 1980.Tarjan,
R. "Sketchy Notes on Edmonds' Incredible Shrinking Blossom Algorithm for General
Matching." Course Notes, Department of Computer Science. Princeton, NJ: Princeton
University, 2002. http://www.cs.dartmouth.edu/~ac/Teach/CS105-Winter05/Handouts/tarjan-blossom.pdf.Vazirani,
V. V. "A Theory of Alternating Paths and Blossoms for Proving Correctness
of the
General Graph Maximum Matching Algorithm." Combinatorica14, 71-109,
1994.West, D. B. "Edmonds' Blossom Algorithm." Introduction
to Graph Theory, 2nd ed. Englewood Cliffs, NJ: Prentice-Hall, pp. 142-145,
2000.