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.

---

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  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." 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.

اخر الاخبار

اخبار العتبة العباسية المقدسة

قسم رعاية الصحن يوضح تفاصيل أعماله في الأيام العشرة الأولى من شهر المحرم

قسم المضيف يعلن تجهيز خمسة منافذ لتوزيع وجبات الطعام بمشاركة 150 متطوعًا في زيارة عاشوراء

قسم الآليات يهيئ أكثر من 300 عجلة لنقل زائري عاشوراء

لليوم السادس.. العتبة العبّاسية المقدّسة تحيي ذكرى فاجعة عاشوراء في الصحن الشريف

المزيد

الآخبار الصحية

لهذا السبب.. إغلاق 25 مركزًا لعلاج الإدمان في مصر ؟

خلافا للاعتقاد الشائع.. علماء يكشفون أسرار بذور البطيخ ؟!

هذا ما يحدث لجسمك عند تناولك الطماطم بانتظام !

تعرف على أطعمة تسرّع "تعافي الجسم" من حروق الشمس

المزيد

الآخبار التكنلوجية

الثلوج تغطي الصحراء الأكثر جفافا في العالم!

بتلسكوب "ألما".. التقاط صورا غير مسبوقة لبدايات الكون !

هل هاتفك مراقب؟.. 5 علامات خطيرة تكشف التجسس عليك

دبي تطلق أول رحلة تجريبية للتاكسي الجوي

المزيد

مواضيع ذات صلة

Minimum Spanning Tree

Maximum Leaf Number

Lobster Graph

Labeled Tree

Internal Path Length

Red-Black Tree

Pseudotree

Pseudoforest

Prüfer Code

Planted Tree

Planted Planar Tree

Graph Strength