At the end of the course students will under know and understand important graph algorithms beyond the reach of standard algorithms and data structures courses. Covered algorithms span most of the important application areas of graphs algorithms. The students also should be able to choose an algorithm best suited for a given task, modifying it when necessary, and estimate its complexity.
Minimum Spanning Trees.
Quick overview of basic algorithms (Kruskal, Jarník [Prim], Borůvka) and their modifications. Advanced algorithms: Fredman-Tarjan, Gabow et al. Randomized algorithms: Karger-Klein-Tarjan. Arborescenses of directed graphs, Edmond's branching algorithm.
Flows in Networks.
Revision - Ford-Fulkerson. Edmonds-Karp, Dinic's algorithm (and its variants), MPM (three Indians) algorithm. Modifications for restricted networks.
Minimum Cuts in Undirected Graphs.
All pairs flows/cuts: Gomory-Hu trees. Global minimum cut: node identification algorithm (Nagamochi-Ibaraki), random algorithms (Karger, Karger-Stein)
Matchings in General Graphs.
Basic algorithm using augmenting paths. Perfect matchings: Edmond's blossom algorithm. Maximum matchings.
Colour refinement. Individualisation-refinement algorithms. Tractable classes of graphs.
Dynamic Algorithms for Hard Problems.
Dynamic programming on trees and circular-arc graphs. Tree-width; dynamic programming on tree-decompositions.
Branching and Kernelization Algorithms for Hard Problems.
Bounded search trees. Kernelization.