Graph Algorithms

In the winter semester 2018/2019, I teach the course on Graph Algorithms (this year in English). Lectures are scheduled on each Thursday from 12:20 in S8.

The lecture covers advanced algorithms for shortest paths, network flows, minimum spanning trees, and some other graph problems. Several graph data structures will be mentioned, too.

If you want to consult anything, please write an e-mail to mares@kam.mff.cuni.cz and we will discuss possibilities.

date topics
11. 10. Network flows: formulation of the problem, basic theorems (min-cut/max-flow, integrality), Ford-Fulkerson algorithm. Applications to bipartite matchings, cuts, and separators.
18. 10. Dinitz algorithm and its behavior on special networks. Scaling algorithm for integer capacities.
25. 10. Globally minimum cuts and separators using flows. Finding cuts probabilistically: the Karger-Stein algorithm.
1. 11. Shortest paths: General relaxation algorithm and a proof of its correctness. Bellman-Ford and Dijkstra algorithms as special cases of relaxation. Data structures for Dijkstra algorithm: various kinds of heaps, array of buckets.
8. 11. Data structures for Dijkstra: multi-level buckets, a sketch of HOT-queues, Dinic's trick for real edge lengths. Potential reduction and elimination of negative lengths.
15. 11. Heuristics for point-to-point shortest path, the A* algorithm. All-pairs shortest paths and transitive closure: Floyd-Warshall algorithm and its generalization to construction of walk expressions. Algebraic point of view.
22. 11. No lecture today.
29. 11. Shortest paths: Making use of matrix multiplication. Seidel's algorithm for undirected unweighted graphs. Introduction to minimum spanning trees: cut lemma, uniqueness, light and heavy edges. Red-blue algorithm and its usual special cases: Jarník's, Borůvka's and Kruskal's algorithm.
6. 12. Minimum spanning trees in planar graphs and minor-closed graph classes (Borůvka's algorithm with contractions and filtering). Density of minor-closed classes: Mader's theorem with a proof, Kostochka-Thomason's without.
13. 12. Minimum spanning trees: Jarník's algorithm with Fibonacci heap, Fredman-Tarjan algorithm (iterated Jarník's algorithm). Lowest common ancestor (LCA), range minima (RMQ) and block decomposition.
20. 12. Suffix trees and their properties. Reducing string problems to graph problems. Ukkonen's algorithm for construction of suffix trees in linear time.
3. 1. Planarity testing and planar embedding (Boyer-Myrvold algorithm). Overture: block structure of graphs via DFS. Embedding a graph in reverse DFS order. Details necessary for linear time.
10. 1. Planarity testing continued (slides): walking rules, details needed for linear time, proof of correctness. A dessert: perfect matching in regular bipartite graphs by degree splitting, relation to edge coloring.

Exams

Exam dates are listed in SIS, please sign up there. If no date suits you, let me know and we can arrange another one. If you want to consult anything before the exam, feel free to ask.

You are expected to know the theory presented at the lecture (algorithms, theorems, and proofs) and to be able to apply it to related problems. Case analysis in the proof of correctness of planarity testing is examined only at request :)

Recommended reading

This page is maintained by Martin Mareš