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

This page is maintained by Martin Mareš