SUBJECT
Title
Combinatorial algorithms I.
Type of instruction
lecture + practical
Level
master
Faculty
Part of degree program
Credits
3+3
Recommended in
Semesters 1-4
Typically offered in
Autumn/Spring semester
Course description
Search algorithms on graphs, maximum adjacency ordering, the algorithm of Nagamochi and Ibaraki. Network flows. The Ford Fulkerson algorithm, the algorithm of Edmonds and Karp, the preflow push algorithm. Circulations. Minimum cost flows. Some applications of flows and circulations. Matchings in graphs. Edmonds` algorithm, the Gallai Edmonds structure theorem. Factor critical graphs. T-joins, f-factors. Dinamic programming. Minimum cost arborescences.
Readings
A. Frank, T. Jordán, Combinatorial algorithms, lecture notes.