Algorithms for Matchings in Graphs
Tzvetalin S. Vassilev, Laura Huntington · Algorithms research · 2012
This paper exp lores maximu m as well as optimal matchings with a strong focus on algorith mic approaches to determining these matchings. It begins with some basic terminology and notions about matchings including Berge's Theorem, Hall's Theorem and the Konig-Egervary Theorem among others. Then an algorithm used for determining maximu m matchings in b ipartite graphs is discussed and examples of its execut ion are explored. Th is discussion is followed by an exploration of weighted graphs and optimal matchings including a statement and discussion of the Hungarian A lgorith m. The Marriage Algorith m is also discussed as are stable marriages and examp les of the execut ion of the Marriage A lgorith m are provided.