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.
The course is scheduled on Thursdays from 10:40 in room S9 and taught in English this year.
If you want to consult anything, please write an e-mail to mares@kam.mff.cuni.cz and we will discuss possibilities.
| date | topics | recording |
|---|---|---|
| 3. 10. | Network flows: formulation of the problem, basic theorems (min-cut/max-flow, integrality), Ford-Fulkerson algorithm. Finding bipartite matchings using flows. | video (partial) |
| 10. 10. | Network flows: Symmetric formulation (effective flow). Dinitz algorithm and its behavior on special networks. | video |
| 17. 10. | Network flows: Scaling algorithm for integer capacities. Disjoint paths, cuts and separators using flows. Finding cuts probabilistically: random contractions and their analysis. | video |
| 24. 10. | Finding cuts probabistically: the Karger-Stein algorithm. Shortest paths: general properties, woes with negative cycles, prefix property and shortest path trees. | video |
| 31. 10. | Shortest paths: Relaxation scheme. Bellman-Ford-Moore algorithm as a special case of relaxation. Dijkstra's algorithm and related data structures: various kinds of heaps. | video |
| 7. 11. | Data structures for Dijkstra's algorithm continued: array of buckets, trees over buckets, multi-level buckets, a sketch of HOT-queues. Dinitz's trick for real edge lengths. Potentials and elimination of negative edges. | video |
| 14. 11. | Obtaining a feasible potential. Heuristics for point-to-point shortest paths: bi-directional Dijkstra, the A* algorithm (examples). All-pairs shortest paths and transitive closure: Floyd-Warshall algorithm and its generalization to construction of walk expressions. | video |
| 21. 11. | All-pairs shortest paths: an algebraic point of view, making use of matrix multiplication. Divide & conquer algorithm for transitive closure. Seidel's algorithm for undirected unweighted graphs. | video |
| 28. 11. | The lecture is cancelled: we organize the Open House Day. | |
| 5. 12. | Plan: Minimum spanning trees: introduction, light and heavy edges. Jarník's algorithm, cut lemma, uniqueness, characterization using light edges. Red-blue algorithm and its usual special cases: Jarník's, Borůvka's and Kruskal's algorithm. Borůvka's algorithm with contractions and filtering. |
Recommended reading
- In English:
- Version 2020 of this course with video recordings (this year's version will be quite similar)
- 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)