Graph Algorithms

In the winter semester 2024/2025, I teach the course on Graph Algorithms. The lecture covers advanced algorithms for shortest paths, network flows, minimum spanning trees, and some other graph problems. Several graph data structures will be mentioned, too.

Time and space coordinates will be agreed upon at Úmluva.

If you want to consult anything, please write an e-mail to mares@kam.mff.cuni.cz and we will discuss possibilities.

Recommended reading

• In English:
  • Alexander Schrijver: Combinatorial Optimization
  • The Saga of Minimum Spanning Trees (my Ph.D. thesis, contains detailed discussion of minimum spanning trees and models of computation)
  • Lecture from 2020 including video recordings
  • Ukkonen's algorithm (translation of a part of my lecture notes)
• In Czech:
  • Skriptíčka Krajinou grafových algoritmů (mají i v knihovně na MS, ale v elektronické verzi jsou kapitoly navíc a opravené chyby)
  • Průvodce labyrintem algoritmů
  • Jiří Demel: Grafy a jejich aplikace (základní algoritmy, Kleeneho algebry)