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
- In English:
- Alexander Schrijver: Combinatorial Optimization
- The Saga of Minimum Spanning Trees (my PhD thesis, contains detailed discussion of minimum spanning trees and models of computation)
- Last year's lecture
- In Czech:
- Skriptíčka Krajinou grafových algoritmů (mají i v knihovně na MS, ale v elektronické verzi jsou kapitoly navíc a opravené chyby)
- Průvodce labyrintem algoritmů
- Jiří Demel: Grafy a jejich aplikace (základní algoritmy, Kleeneho algebry)