Matchings in Graphs Accueil - Enseignements

Some lectures given within M. Habib's class "Algorithmique des Graphes" for the Master Parisien de Recherche en Informatique (Master 2).
Topics include:

Maximum matching in graphs: Edmonds's blossom algorithm; derivation of the Tutte-Berge Formula.
Another proof of the Tutte-Berge Formula. The Edmonds-Gallai decomposition. Petersen's Theorem.
(Perfect) matching polytope: characterisation for bipartite graphs and for general graphs, applications.
Lecture 1.
Lecture 2.
Lecture 3.
Exercises.