Graph algorithms (Master 2 ICS, 2025-2026)
Laurent Beaudou teaches the first 10 hours, and Florent Foucaud teaches the other 10 hours.
Ressources for Florent Foucaud's part
Lectures 1 and 2 (October 23 and 24)
- 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 27)
- Topics: dynamic programming for maximum weighted independent set on trees
- 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.
Lecture 4 (December 5)
- Topics: dominating set for trees - treewidth (definition, properties)
- slides by Ignasi Sau
Lecture 5 (December 12)
- 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