Spring 2025

Teacher: Arnaud Casteigts
Assistant: Matteo De Francesco
Overview: [slides]

  1. Basics of Graph Theory: [lecture notes]
  2. Traversals, Connectivity, Shortest paths: [lecture notes]
  3. Minimum Spanning Trees (and Matroid): [lecture notes]
  4. Basics of Computational Complexity: [lecture notes] - [slides]
  5. Graph coloring: [slides]
  6. Maximum matchings: [lecture notes]
  7. Approximation algorithms: [lecture notes]
  8. Random Walks (and Markov chains): [slides]
  9. Distributed algorithms: [slides]
  10. Basic concepts of Temporal Graphs: [lecture notes]
  11. Temporal components and temporal spanners: [lecture notes]

Mini-class projects

Monday 19th May, 2025

Morning session (11am):

  • Shcherbakov: Reconstruction conjecture
  • Sutter: A* and related algorithms
  • Salane and Thakur: The max-flow min-cut theorem
  • Rahman: Auction algorithms for bipartite matching
  • Goldfarb: Dynamic Graph algorithms

Afternoon session (2pm):

  • Zebad and Gassilewski: Kuratowski’s and Wagner’s theorem
  • Arm: Distributed algorithms in the LOCAL model
  • Selvam and Amehunke: Interval graphs (and who killed the Duke of Densmore)
  • Zarola and Bolotina: The max-flow min-cut theorem

Monday 26th May, 2025

Morning session (11am):

  • Horvath and Folly-Dogba: Eulers formula
  • Mishra and Agarwal: Community detection
  • Gay: Quantum random walks on graphs
  • Diallo and Nada-Abi: Graph Spanners
  • Akoumba: Geometric Routing

Afternoon session (2pm):

  • Maggiorano: Cycle detection for train schedule applications
  • Gong and Fang: Graph Isomorphism
  • Yang and Bian: Hamiltonian paths