Course for international guest/part time students
- Faculty
- Faculty of Science
- Organization
- TTK Department of Operations Research
- Code
- kombal1u0um17em
- Title
- Combinatorial algorithms 1 (l)
- Usual semester
- Autumn
- Published semester
- 2026/27/1
- ECTS
- 3
- Language
- en
- Learning outcomes
- Knowledge: getting familiar with the most important combinatorial algorithms Ability: to understand and use combinatorial algorithms Attitude: the need to extend the mathematical knowledge, to gain new analytic skills Autonomy and Responsibility: based on the gained knowledge in combinatorial algorithms, the students are able to decide which tools are the most suitable to solve applied problems
- Course content
- Traversal of graphs, MI-orderig, Nagamochi-Ibaraki algorithm, strongly connected graphs, sparse witnesses, ear decompositions. Karger's algorithm. Chordal graphs, simplicial order. Flow equivalent trees, Gomory-Hu tree. Tree-width, algorithms on graphs with small tree-width. Combinatorial rigidity. Degree-bounded orientation. Dynamic programming, minimum cost arborescence.
- Assessment method
- exam
- Bibliography
- lecture notes