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. Plan: All-pairs shortest paths: making use of matrix multiplication. Seidel's algorithm for undirected unweighted graphs. Minimum spanning trees: Cut lemma, uniqueness, light and heavy 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

This page is maintained by Martin Mareš