Graph Algorithms

In the winter semester 2021/2022, 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 10:40 in room S322 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
6. 10. Network flows: formulation of the problem, basic theorems (min-cut/max-flow, integrality), Ford-Fulkerson algorithm. Applications to bipartite matchings and disjoint paths.
13. 10. Network flows: Dinitz algorithm and its behavior on special networks. Scaling algorithm for integer capacities.
20. 10. Disjoint paths, cuts and separators using flows. Finding cuts probabilistically: the Karger-Stein algorithm.
27. 10. Shortest paths: general properties, woes with negative cycles, prefix property. Relaxation scheme and a proof of its correctness. Bellman-Ford-Moore algorithm as a special case of relaxation. Dijkstra's algorithm and related data structures: various kinds of heaps.
3. 11. Data structures for Dijkstra: 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.
10. 11. Shortest path trees. 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. All-pairs shortest paths: making use of matrix multiplication.
17. 11. No lecture today, we have a holiday!
24. 11. Divide & conquer algorithm for transitive closure. Seidel's algorithm for undirected unweighted graphs. Introduction to minimum spanning trees: light and heavy edges. Minimum spanning trees: Cut lemma, uniqueness, characterization using light edges. Red-blue algorithm.
1. 12. Plan: Red-blue algorithm and its usual special cases: Jarník's, Borůvka's and Kruskal's algorithm. 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).

Recommended reading

This page is maintained by Martin Mareš