Graph Algorithms

In the winter semester 2019/2020, I teach the course on Graph Algorithms (this year in English). Lectures are scheduled on each Thursday from 15:40 in S11.

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.

If you want to contact me and consult anything, you are welcome to visit me in room S322 or to write me an e-mail to mares@kam.mff.cuni.cz.

date topics
10. 10. Network flows: formulation of the problem, basic theorems (min-cut/max-flow, integrality), Ford-Fulkerson algorithm. Applications to bipartite matchings and disjoint paths.
17. 10. Dinitz algorithm and its behavior on special networks. Scaling algorithm for integer capacities.
24. 10. Cuts and separators using flows. Finding cuts probabilistically: the Karger-Stein algorithm.
31. 10. Shortest paths: General relaxation algorithm and a proof of its correctness. Bellman-Ford-Moore algorithm as a special case of relaxation.
7. 11. Dijkstra algorithm and related data structures: various kinds of heaps, array of buckets, multi-level buckets, a sketch of HOT-queues.
14. 11. Plan: Dinic's trick for real edge lengths. Potential reduction and elimination of negative lengths. Heuristics for point-to-point shortest path, the A* algorithm. All-pairs shortest paths and transitive closure: Floyd-Warshall algorithm and its generalization to construction of walk expressions. Algebraic point of view.

Recommended reading

This page is maintained by Martin Mareš