Graph Algorithms

In the winter semester 2022/2023, 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 Wednesdays from 12:20 in room S9 and taught in English this year.

If you miss a lecture, you can watch video recordings from year 2020; this year's lectures are quite similar.

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

date topics
5. 10. Network flows: formulation of the problem, basic theorems (min-cut/max-flow, integrality), Ford-Fulkerson algorithm. Finding bipartite matchings using flows.
12. 10. Network flows: Symmetric formulation (effective flow). Dinitz algorithm and its behavior on special networks.
19. 10. Network flows: Scaling algorithm for integer capacities. Disjoint paths, cuts and separators using flows. Finding cuts probabilistically: the Karger-Stein algorithm.
26. 10. The Karger-Stein algorithm finished. Shortest paths: general properties, woes with negative cycles, prefix property. Shortest path trees. Relaxation scheme.
2. 11. Shortest paths: Correctness of the relaxation scheme. Bellman-Ford-Moore algorithm as a special case of relaxation. Dijkstra's algorithm and related data structures: various kinds of heaps.
9. 11. There is no lecture today – we have the Dean's sports day.
16. 11. Data structures for Dijkstra's algorithm continued: array of buckets, trees over buckets, multi-level buckets, a sketch of HOT-queues. Dinic's trick for real edge lengths. Potential reduction and elimination of negative lengths.
23. 11. 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.
30. 11. Floyd-Warshall: An algebraic point of view. All-pairs shortest paths: making use of matrix multiplication. Divide & conquer algorithm for transitive closure. Seidel's algorithm for undirected unweighted graphs.
7. 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.
14. 12. Plan: Minimum spanning trees: Kruskal's algorithm and Union-Find problem. Borůvka's algorithm with contractions and filtering. Minimum spanning trees in planar graphs and minor-closed graph classes. Density of minor-closed classes and the theorems of Mader and Kostochka+Thomason (without proofs). Jarník's/Dijkstra's algorithm with Fibonacci heap, Fredman-Tarjan algorithm (iterated Jarník's algorithm).
21. 12. Plan: Lowest common ancestor (LCA), range minima (RMQ), and block decomposition. Frederickson decomposition of a graph. Union-Find with the tree of Unions known in advance. A dessert: perfect matching in regular bipartite graphs by degree splitting, relation to edge coloring.
4. 1. Plan: Representation of trees using ET-sequences and ET-trees. Fully dynamic connectivity in undirected graphs (Holm, de Lichtenberg, Thorup). [Not present in the lecture notes, please see chapters 5.2 and 5.3 of my thesis.]

Exams

Exam dates will be listed in SIS, please sign up there. If no date suits you, let me know and we can arrange another 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.

Recommended reading

This page is maintained by Martin Mareš