TOPICS
Search

Blossom Algorithm


The blossom algorithm (Edmonds 1965) finds a maximum independent edge set in a (possibly weighted) graph. While a maximum independent edge set can be found fairly easily for a bipartite graph using the Hungarian maximum matching algorithm, the general case is more difficult. Edmonds's blossom algorithm starts with a maximal independent edge set, which it tries to extend to a maximum independent edge set using the property that a matching is maximum iff the matching does not admit an augmenting path.

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.


See also

Augmenting Path, Hungarian Maximum Matching Algorithm, Matching, Matching Number, Maximum Independent Edge Set

This entry contributed by Stan Wagon

Explore with Wolfram|Alpha

References

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. ACM 38, 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 O(sqrt(|V|)·|E|) 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 O(sqrt(VE)) General Graph Maximum Matching Algorithm." Combinatorica 14, 71-109, 1994.West, D. B. "Edmonds' Blossom Algorithm." Introduction to Graph Theory, 2nd ed. Englewood Cliffs, NJ: Prentice-Hall, pp. 142-145, 2000.

Cite this as:

Wagon, Stan. "Blossom Algorithm." From MathWorld--A Wolfram Web Resource, created by Eric W. Weisstein. https://mathworld.wolfram.com/BlossomAlgorithm.html

Subject classifications