Syllabus
Network flows: Goldberg's algorithm and its kin.
Accelerating flow algorithms on sparse graphs using Sleator-Tarjan Trees.
Description of minimum cuts by Gomory-Hu Trees.
Data structures for integers: Van Emde-Boas Trees, Q-Heaps, atomic heaps.
Minimum spanning trees: Integer algorithms, verification of minimality, Pettie's optimal algorithm.
Annotation
This course covers advanced graph algorithms, techniques of their design, and related data structures. It extends the Graph algorithms course (NDMI010).