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]
• Cours 10 : Basic concepts of Temporal Graphs: [lecture notes]
• Cours 11 : Temporal components and temporal spanners: [lecture notes]

Mini-class projects

Objective: give a mini-class on a particular topic. Using slides is not mandatory, but strongly recommended (possibly with hybrid content on the whiteboard).

Timing: 10 to 15 minutes + 5 minutes of questions.

Typical plan:

1. Broader context and overview of known results on this topic (2 to 5 min)
2. Presentation of a particular algorithm or theorem (4 to 7 min)
3. If applicable, a demo coded in networkX or JBotSim (2 to 4 min)
4. If applicable, main open questions (∼2 min)

You are required to attend all the talks. An evaluation form will have to be filled by each participant for all the talks.

Program (please be on time):

Monday 19th May

Morning session (11h15):

• 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 (14h15):

• 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

Morning session (11h15):

• 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 (14h15):

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