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. 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. Duality of red and blue rule in planar graphs. video
12. 12. Minimum spanning trees: Borůvka's algorithm with contractions and filtering. MST in planar graphs and minor-closed graph classes. Density of minor-closed classes and the theorems of Mader and Kostochka+Thomason (without proofs). Kruskal's algorithm and Union-Find problem. Jarník's/Dijkstra's algorithm with Fibonacci heap, video
19. 12. Minimim spanning trees: Fredman-Tarjan algorithm (iterated Jarník's algorithm). Kruskal's algorithm and the Union-Find problem, analysis with O(log* n) bound. Review of best known MST algorithms. video
9. 1. Plan: Lowest common ancestor (LCA) and range minima (RMQ), reduction from LCA to RMQ±1, RMQ±1 via block decomposition, reduction of RMQ back to LCA. Union-Find with unions known in advance via Frederickson's decomposition and binary coding.

Exams

Exam dates are listed in SIS, please sign up there. If no date suits you, let me know and we can arrange a different one. If you want to consult anything before the exam, feel free to ask.

You are expected to know the theory presented at the lecture (algorithms, theorems, and proofs) and to be able to apply it to related problems.

You are allowed to bring a cheat sheet on a single A4 page. The only restriction is that it must be your own work (hand-written or typed).

Recommended reading

This page is maintained by Martin Mareš