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


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

Stránku spravuje Martin Mareš