Graph Algorithms
In the winter semester 2013/2014, I teach the course on Graph Algorithms (this year in English). Lectures are scheduled on each Wednesday from 17:20 in S5.
| date | topics |
|---|---|
| 9. 10. | Network flows: formulation of the problem, basic theorems (min-cut/max-flow, integrality), Ford-Fulkerson algorithm. Applications to bipartite matchings, cuts and separators. |
| 16. 10. | Network flows: Dinitz algorithm and thorough analysis of its variants. |
| 23. 10. | No lecture today. Celebrate Dean's Sports Day. |
| 30. 10. | Network flows: Capacity scaling. Cuts, separators and graph connectivity. Introduction to shortest paths: graph metric, problems with negative cycles, prefix property, shortest path trees. General relaxation algorithm, Bellman-Ford algorithm. |
| 6. 11. | Shortest paths: Dijkstra's algorithm and related data structures. Various kinds of heaps, bucket structures, multi-level buckets. A remark on complexity of sorting. |
| 13. 11. | Shortest paths: 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. |
| 20. 11. | Shortest paths: Generalized matrix multiplication. Transitive closure by Divide and conquer. Seidel's algorithm for distances in non-weighted undirected graphs. Introduction to minimum spanning trees: basic structural theorems (exchanges, uniqueness, characterization using light edges). |
| 27. 11. | Minimum spanning trees: The 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. |
| 4. 12. | Minimum spanning trees: Fredman-Tarjan algorithm (iterated Jarník). Lowest Common Ancestors (LCA) in trees, interval minima (RMQ) and decomposition to blocks. |
| 11. 12. | 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.] |
| 18. 12. | Suffix trees and their properties. Relations to suffix arrays and LCP arrays. Kärkkäinen-Sanders algorithm for their construction in linear time. |
| 8. 1. | Planarity testing and planar embedding (a sketch). |
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)
- Loňská přednáška
- Jiří Demel: Grafy a jejich aplikace (základní algoritmy, Kleeneho algebry)