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