Graph Algorithms (14X061)

Enseignant : Arnaud Casteigts
Assistants : Matteo De Francesco

Every Monday, room 301 (Battelle campus) - 11:15 (course) - 14:15 (exercises).

Other pages for this class

• Moodle (all documents + communications)
• Unige (administrative page)

Lecture notes

This section will be updated after each class.

• Preambule: [slides]
• Cours 1 : Basics of Graph Theory: [lecture notes]
• Cours 2 : Traversals, Connectivity, Shortest paths: [lecture notes]
• Cours 3 : Minimum Spanning Trees (and Matroid): [lecture notes]
• Cours 4 : Basics of Computational Complexity: [lecture notes] - [slides]
• Cours 5 : Graph coloring: [slides]
• Cours 6 : Maximum matchings: [lecture notes]
• Cours 7 : Approximation algorithms: [lecture notes]
• Cours 8 : Random Walks (and Markov chains): [slides]
• Cours 9 : Distributed algorithms: [slides]

Mini-class projects

This the instructions here: [mini-class project]