Hungarian Maximum Matching Algorithm

The Hungarian algorithm finds a maximum independent edge set on a graph. The algorithm starts with any matching  and constructs a tree via a breadth-first search to find an augmenting path, namely a path  that starts and finishes at unmatched vertices whose first and last edges are not in  and whose edges alternate being outside and inside . If the search succeeds, the symmetric difference of  and the edges in  yields a matching with one more edge than . That edge is added, and then another search is performed for a new augmenting path. If the search is unsuccessful, the algorithm terminates and  must be the largest-size matching.

As an added bonus, the tree data provides a vertex cover.

If the tree search is unsuccessful, as it is at the end, then the size of the vertex cover is the same as the size of the matching, which proves that the final matching has the maximum size possible.

---

REFERENCES

Brualdi, R. A. Introductory Combinatorics, 4th ed. New York: Elsevier, 1997.

Cook, W. J.; Cunningham, W. H.; Pulleyblank, W. R.; and Schrijver, A. Combinatorial Optimization. New York: Wiley, 1998.

Hopcroft, J. and Karp, R. "An  Algorithm for Maximum Matching in Bipartite Graphs." SIAM J. Comput. 2, 225-231, 1975.

 Wagon, S. "The Hungarian Maximum Matching Algorithm." http://demonstrations.wolfram.com/TheHungarianMaximumMatchingAlgorithm/.West, D. B. Introduction to Graph Theory, 2nd ed. Englewood Cliffs, NJ: Prentice-Hall, pp. 127-130, 2000.

Zwick, U. "Lecture Notes on: Maximum Matching in Bipartite and Non-Bipartite Graphs." http://www.cs.tau.ac.il/~zwick/grad-algo-0910/match.pdf. 2009.

اخر الاخبار

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

العتبة العباسية المقدسة تنظم احتفالها المركزي بذكرى ولادة الإمامين الباقر والهادي (عليهما السلام)

وفد متحف الكفيل يطّلع على المخطوطات النادرة والسجاد اليدوي والزخارف المعمارية في مدينة أصفهان

قسم التطوير يختتم دورة التعامل مع وسائل الإعلام لعددٍ من المنتسبين

سماحة السيد الصافي يطّلع على سير العملية التعليمية في مجموعة مدارس العميد التربوية

المزيد

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

ثورة طبية.. الذكاء الاصطناعي يكشف سرطان الكلى في وقت قياسي

لتعزيز الطاقة والتغلب على التعب.. عليك بـ7 طرق بسيطة

لتحسين الهضم والتحكم في الشهية.. ما أفضل وقت لتناول التمر؟

خبراء يكشفون تأثير الاستحمام في الظلام على جودة النوم !

المزيد

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

إزالة ثاني أكسيد الكربون من الغلاف الجوي.. ما دور المحيطات والبحار؟

نظائر الهيليوم مقياس لاكتشاف رواسب الذهب.. كيف ذلك؟

الصين تطلق أول ناقلة نفط خام ذكية في العالم تعمل بالميثانول

الزمن على المريخ أسرع من الأرض.. دراسة علمية تكشف الفوارق

المزيد

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

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