Graph Algorithms (14X061)
Enseignant : Arnaud Casteigts
Assistants : Himika Das
Every Monday, room 301 (Battelle campus) - 11am (course) - 2pm (exercises).
Other pages for this class
- Moodle (all documents + communications)
- Unige (administrative page)
- Previous years (may differ from this year)
Lecture notes
This section will be updated after each class.
- Preambule: [slides]
- Basics of graph theory: [lecture notes]
- Basic algorithms: [lecture notes]
- Minimum Spanning Trees (and Matroid): [lecture notes]
- Computational complexity: [slides] - [lecture notes]
- Graph coloring: [slides]
- Maximum Matching: [lecture notes]
- Approximation algorithms: [lecture notes]
Mini-class projects (in May 2026)
Slides with list of topics: [slides]
Objective: give a mini-class on a particular topic. Using slides is strongly recommended, possibly with hybrid content on the whiteboard.
Timing: 10 to 15 minutes + 5 minutes of questions.
Grading: 1/4 of the final grade (exam 3/4)
Typical plan:
- Broader context and overview of known results on this topic (3 to 5 min)
- Presentation of a particular algorithm or theorem (5 to 8 min)
- If applicable, main challenges or conjectures (∼3 min)
- Questions