MTH6105 Algorithmic Graph Theory

Week 9: Maximum Matchings 2

  Covered this week:
Lecture 1:
Non-bipartite graphs: obstacles to finding M-augmenting paths. Notes PDF file icon
Lecture 2:
König's Algorithm for bipartite matching. Notes PDF file icon
Lecture 3:
König's minimax theorem relating maximum matchings and minimum covers. Notes PDF file icon

Week 9 Coursework: watch the boxes below!
Coursework 8
Solutions
Download pdf
Submit: 14.03
Jpegs: Question 3, Question 4
Download pdf

Extra: some notes of mine on the complexity of the vertex cover problem for graphs in general: see section 4.2.2. And the view from theoremoftheday.org

Week 8 Week 10 Back to MTH6105 main page School of Maths Sciences