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 consult anything, please write an e-mail to mares@kam.mff.cuni.cz and we will discuss possibilities.
| 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. | 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. |
| 21. 11. | No lecture today. |
| 28. 11. | All-pairs shortest paths: An algebraic point of view. Making use of matrix multiplication. Seidel's algorithm for undirected unweighted graphs. Introduction to minimum spanning trees. |
| 5. 12. | 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. |
| 12. 12. | Minimum spanning trees in planar graphs and minor-closed graph classes. Density of minor-closed classes via Mader's theorem. Kostochka-Thomason's theorem (proof omitted). |
| 19. 12. | Minimum spanning trees: Jarník's algorithm with Fibonacci heap, Fredman-Tarjan algorithm (iterated Jarník's algorithm). Lowest common ancestor (LCA), range minima (RMQ), and block decomposition. |
| 9. 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 Ph.D. thesis.] |
Exams
Exam dates are listed in SIS, please sign up there. 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
- 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)