Graph Algorithms

In the winter semester 2020/2021, 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 lectures will be held online on Wednesdays from 9:00. You should have received a Zoom link by e-mail.

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
7. 10. Network flows: formulation of the problem, basic theorems (min-cut/max-flow, integrality), Ford-Fulkerson algorithm. Applications to bipartite matchings. video board
14. 10. Network flows: Dinitz algorithm and its behavior on special networks. video board
21. 10. Network flows: Scaling algorithm for integer capacities. Disjoint paths, cuts and separators using flows. Finding cuts probabilistically: the Karger-Stein algorithm. video board
28. 10. No lecture today, choose your own holiday :)
4. 11. Karger-Stein algorithm continued. Shortest paths: general properties, woes with negative cycles, shortest path trees. Relaxation scheme and a proof of its correctness. video board
11. 11. Shortest paths: Bellman-Ford-Moore algorithm as a special case of relaxation. Dijkstra's algorithm and related data structures: various kinds of heaps, array of buckets. video board
18. 11. Data structures for Dijkstra: trees over buckets, multi-level buckets, a sketch of HOT-queues. Shortest paths: Dinic's trick for real edge lengths. Potential reduction and elimination of negative lengths. video board
25. 11. Heuristics for point-to-point shortest paths, the A* algorithm. All-pairs shortest paths and transitive closure: Floyd-Warshall algorithm and its generalization to construction of walk expressions. An algebraic point of view. video board
2. 12. All-pairs shortest paths: making use of matrix multiplication. Divide & conquer algorithm for transitive closure. Seidel's algorithm for undirected unweighted graphs. Introduction to minimum spanning trees: light and heavy edges. video board
9. 12. Minimum spanning trees: 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. Union-Find problem. video board
16. 12. Minimum spanning trees: 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). [The recording contains only the Fredman-Tarjan algorithm, sorry about that. You can find the rest in chapters 3.1 and 3.2 of my thesis.] video board
6. 1. 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.] video board

Exams

Exam dates are listed in SIS, please sign up there. I prefer examining in person, but it is hard for you to get to Prague, there are also distance exams listed. 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š