Topics in Structural Graph Theory and Algorithms - NDMI105

• Anglický název: Topics in Structural Graph Theory and Algorithms
• Zajišťuje: Informatický ústav Univerzity Karlovy (32-IUUK)
• Fakulta: Matematicko-fyzikální fakulta
• Platnost: od 2022
• Semestr: letní
• E-Kredity: 3
• Rozsah, examinace: letní s.:2/0, Zk [HT]
• Počet míst: neomezen
• Minimální obsazenost: neomezen
• 4EU+: ne
• Virtuální mobilita / počet míst pro virtuální mobilitu: ne
• Stav předmětu: nevyučován
• Jazyk výuky: angličtina
• Způsob výuky: prezenční
• Další informace: https://iuuk.mff.cuni.cz/~ipenev/NDMI105S2022.html
• Garant: Irena Penev, Ph.D.
• Třída: Informatika Mgr. - volitelný
• Kategorizace předmětu: Informatika > Diskrétní matematika

Anotace

This course covers topics in structural graph theory and algorithms. The syllabus varies from year to year, but the focus is on decomposition and structure theorems for hereditary graph classes, and on algorithmic applications of such theorems.

Poslední úprava: Pangrác Ondřej, RNDr., Ph.D. (06.05.2019)

Podmínky zakončení předmětu

There will be an oral exam consisting of a presentation of one research paper.

Poslední úprava: Penev Irena, Ph.D. (14.06.2019)

Literatura

Lecture notes and research papers.

Poslední úprava: Pangrác Ondřej, RNDr., Ph.D. (06.05.2019)

Sylabus

The syllabus varies from year to year and is given at the beginning of the semester. Topics usually include perfect graphs and related classes, as well as polynomial-time algorithms (especially those solving the recognition, optimal coloring, maximum clique, and maximum stable set problems) for those classes.

Syllabus for Winter 2019/2020: https://iuuk.mff.cuni.cz/~ipenev/NDMI105Winter2019.html

Poslední úprava: Penev Irena, Ph.D. (30.09.2019)