SUBJECT

Title

Combinatorial algorithms II.

Type of instruction

lecture

Level

master

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.