Graph Algorithms
In the winter semester 2016/2017, I teach the course on Graph Algorithms (this year in English). Lectures are scheduled on each Tuesday from 9:00 in S9. (Exceptions: on 25. 10., 29. 11., and 20. 12. we are in the corridor S321.)
date | topics |
---|---|
11. 10. | Network flows: formulation of the problem, basic theorems (min-cut/max-flow, integrality), Ford-Fulkerson algorithm. Applications to cuts and separators. |
18. 10. | Network flows: Applications to disjoint paths and bipartite matching. Dinitz algorithm and its behavior on special networks. |
25. 10. | Cuts, separators and graph connectivity via flows. Probabilistic algorithm for minimum cut in undirected graphs (Karger-Stein). |
1. 11. | Network flows: Capacity scaling. Introduction to shortest paths: graph metric, problems with negative cycles, prefix property, shortest path trees. General relaxation algorithm. Homework: What happens if we maintain open vertices in a queue or in a stack? How does the relaxation algorithm behave in presence of negative cycles? |
8. 11. | No lecture today, exercises instead. It's dean's sports day. |
15. 11. | Bellman-Ford algorithm. Dijkstra's algorithm and related data structures. Various kinds of heaps, bucket structures, multi-level buckets. A remark on complexity of sorting. |
22. 11. | Shortest paths: Dinitz's trick for non-integer edges. Potential-based reduction and elimination of negative edges. Heuristics for point-to-point shortest paths, the A^{*} algorithm. Computing distance matrices: Floyd-Warshall algorithm and its generalization to construction of walk expressions. |
29. 11. | Shortest paths: Homomorphic Floyd-Warshall. Generalized matrix multiplication. Transitive closure by Divide and conquer. Seidel's algorithm for distances in non-weighted undirected graphs. |
6. 12. | Minimum spanning trees: basic structural theorems (exchanges, uniqueness, characterization using light edges). Red-black algorithm and its duality. The three classical algorithms – Jarník, Borůvka, and Kruskal. MST in planar graphs via contractions. Generalization to minor-closed graph classes. |
13. 12. | Minimum spanning trees: Minor-closed graph classes and bounds on their density. Mader's theorem with a proof, Kostochka-Thomason theorem without. Fredman-Tarjan algorithm (iterated Jarník). |
20. 12. | Data structures for trees: Lowest Common Ancestors (LCA), interval minima (RMQ) and decomposition to blocks. Union-Find with unions known in advance via Frederickson's decomposition and binary coding. A brief example using Jordano decomposition and re-rooting (path with a given sum). |
3. 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.] |
10. 1. | Suffix trees and their properties. Relations to suffix arrays and LCP arrays. Kärkkäinen-Sanders algorithm for their construction in linear time. |
Exams
Please sign up for exams in SIS. If you prefer a different time, please let me know.
You are expected to know all lecture material and apply it to different problems. Details of the planarity testing algorithm are excluded.
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)
- In Czech:
- Skriptíčka Krajinou grafových algoritmů (mají i v knihovně na MS; podívejte se ale na seznam známých chyb)
- Rozpracovaná knížka o algoritmech a datových strukutrách
- Loňská přednáška
- Jiří Demel: Grafy a jejich aplikace (základní algoritmy, Kleeneho algebry)