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.
|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).|
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.
- 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: