Graph algorithms (Master 2 ICS, 2024-2025)
Laurent Beaudou teaches the first 10 hours, and Florent Foucaud teaches the other 10 hours.
Ressources for Laurent Beaudou's part
- Course notes on the planar separator theorem: notes (theorem) / notes (applications)
- Source for matchings: book Combinatorial Optimization: Polyhedra and Efficiency by Alexander Schrijver (Springer, 2002).
Ressources for Florent Foucaud's part
Lectures 1 and 2 (November 7 and 14)
- Topics: greedy algorithms for coloring and independent set on interval graphs and chordal graphs
- handwritten course notes
- Source (chordal/triangulated graphs): chapter 4 in the book Algorithmic Graph Theory and Perfect Graphs by Martin C. Golumbic (Elsevier, 2004).
Lecture 3 (November 28)
- Topics: solution for minimum dominating set on intervals, dynamic programming for maximum weighted independent set on trees
- source (independent sets): chapter 7 in Parameterized algorithms
by Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Daniel Marx, Marcin Pilipczuk, Michal Pilipczuk and Saket Saurabh
Springer, 2015.
Lecture 4 (December 6)
- Topics: dominating set for trees - treewidth (definition, properties)
- slides by Ignasi Sau
Lecture 5 (December 13)
- Topics: further properties and recap on tree decompositions - dynamic programming for maximum independent set (and 3-coloring) on tree decompositions
- Lecture notes typed by Lucas Lorieau on lectures 3, 4, 5
- source: chapter 7 in Parameterized algorithms
by Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Daniel Marx, Marcin Pilipczuk, Michal Pilipczuk and Saket Saurabh
Springer, 2015. - slides by Ignasi Sau