SubjectsSubjects(version: 945)
Course, academic year 2023/2024
   Login via CAS
Topics in Structural Graph Theory and Algorithms - NDMI105
Title: Topics in Structural Graph Theory and Algorithms
Guaranteed by: Computer Science Institute of Charles University (32-IUUK)
Faculty: Faculty of Mathematics and Physics
Actual: from 2022
Semester: summer
E-Credits: 3
Hours per week, examination: summer s.:2/0, Ex [HT]
Capacity: unlimited
Min. number of students: unlimited
4EU+: no
Virtual mobility / capacity: no
State of the course: not taught
Language: English
Teaching methods: full-time
Teaching methods: full-time
Additional information: https://iuuk.mff.cuni.cz/~ipenev/NDMI105S2022.html
Guarantor: Irena Penev, Ph.D.
Class: Informatika Mgr. - volitelný
Classification: Informatics > Discrete Mathematics
Annotation
Last update: RNDr. Ondřej Pangrác, Ph.D. (06.05.2019)
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.
Course completion requirements
Last update: Irena Penev, Ph.D. (14.06.2019)

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

Literature
Last update: RNDr. Ondřej Pangrác, Ph.D. (06.05.2019)

Lecture notes and research papers.

Syllabus
Last update: Irena Penev, Ph.D. (30.09.2019)

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

 
Charles University | Information system of Charles University | http://www.cuni.cz/UKEN-329.html