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.

اخر الاخبار

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

مستشفى الكفيل يدخل قائمة الاعتماد الدولية بجودة الخدمة وسلامة المرضى

جامعة العميد تقيم ورشة عمل تدريبية في مجال التعليم الطبي الحديث

سماحة السيد الصافي يدعو إلى الاستمرار في تحقيق تراث العلماء الأعلام وتسليط الضوء على فكرهم

شعبة الخطابة الحسينية تختتم الموسم الثامن من مشروع الدورات الصيفية في كربلاء

المزيد

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

الأطعمة الحارة.. "سر صغير" يغير صحة قلبك وعقلك

وباء صامت.. الملايين حول العالم مصابون بالسكري دون أن يعلموا !

لماذا ينصح بتناول تفاحة يوميا؟

8 فواكه طبيعية تمنحك نوما هنيئا.. وتخلصك من الأرق

المزيد

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

ثلاث علامات على وجود مشاكل خطيرة في محرك السيارة ؟

ماذا نعرف عن اللقاح الروسي ضد السرطان؟

مركبة فضاء تعثر على دليل عن وجود حياة قديمة على المريخ

لتدريب الذكاء الاصطناعي.. الصين تخطط لإنشاء شبكة حوسبة موحدة

المزيد

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

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