Syllabus
Network flows: Dinic's algorithm, Malhotra-Kumar-Maheshwari blocking flows, methods for sparse networks and networks with integer capacities.
Testing of k-connectivity: searching for cuts and separators using flows, Karger-Stein's randomized algorithm.
Shortest paths: General relaxation scheme, Dijkstra's algorithm and related data structures (heaps, single- and multi-level buckets). Potential reduction and heuristics based on it. Algebraic connections with matrix multiplications, Kleene algebras. Transitive closures and Seidel's algorithm.
Minimum spanning trees: Fredman-Tarjan's algorithm for general graphs, Fredman-Willard's for integer weights and special algorithms for planar graphs and minor-closed graph classes.
Tree decomposition techniques: clusterization and micro/macro-tree decomposition, the tree ancestor problem and Union-Find problem.
Reduction of string problems to graph problems: suffix trees and their construction in linear time.
Testing of planarity and construction of plannar embeddings.
Annotation
This course covers advanced graph algorithms and techniques of their design.