All Title Author
Keywords Abstract


Algorithms for Matchings in Graphs

DOI: 10.5923/j.algorithms.20120104.02

Keywords: Graph Theory, Matchings, Greedy Algorithms, Stable Marriage

Full-Text   Cite this paper   Add to My Lib

Abstract:

This paper explores maximum as well as optimal matchings with a strong focus on algorithmic approaches to determining these matchings. It begins with some basic terminology and notions about matchings including Berge’s Theorem, Hall’s Theorem and the K nig-Egerváry Theorem among others. Then an algorithm used for determining maximum matchings in bipartite graphs is discussed and examples of its execution are explored. This discussion is followed by an exploration of weighted graphs and optimal matchings including a statement and discussion of the Hungarian Algorithm. The Marriage Algorithm is also discussed as are stable marriages and examples of the execution of the Marriage Algorithm are provided.

Full-Text

comments powered by Disqus