SUBJECT
Title
Combinatorial algorithms II.
Type of instruction
lecture
Level
master
Faculty
Part of degree program
Credits
3
Recommended in
Semesters 1-4
Typically offered in
Autumn/Spring semester
Course description
Connectivity of graphs, sparse certificates, ear decompositions. Karger`s algorithm for computing the edge connectivity. Chordal graphs, simplicial ordering. Flow equivalent trees, Gomory Hu trees. Tree width, tree decomposition. Algorithms on graphs with small tree width. Combinatorial rigidity. Degree constrained orientations. Minimum cost circulations
Readings
A. Frank, T. Jordán, Combinatorial algorithms, lecture notes.