SubjectsSubjects(version: 928)
Course, academic year 2022/2023
   Login via CAS
Graph Minors and Tree Decompositions - NDMI059
Title: Grafové minory a stromové rozklady
Guaranteed by: Department of Applied Mathematics (32-KAM)
Faculty: Faculty of Mathematics and Physics
Actual: from 2020 to 2022
Semester: winter
E-Credits: 3
Hours per week, examination: winter s.:2/0, Ex [HT]
Capacity: unlimited
Min. number of students: unlimited
Virtual mobility / capacity: no
State of the course: taught
Language: English, Czech
Teaching methods: full-time
Guarantor: doc. RNDr. Jiří Fiala, Ph.D.
Class: Informatika Mgr. - Diskrétní modely a algoritmy
Classification: Informatics > Discrete Mathematics
Annotation -
Last update: FIALA/MFF.CUNI.CZ (08.10.2008)
Special course for advanced undergraduate and graduate students devoted to graph minor theory in its relationship to treewidth.
Course completion requirements -
Last update: doc. RNDr. Jiří Fiala, Ph.D. (07.10.2019)

To learn the subject as described in the syllabus and be able to solve appropriate problems.

Literature - Czech
Last update: FIALA (15.03.2006)

Diestel, R.: Graph Theory, graduate texts in mathematics, vol. 173., Springer Verlag, May 1997.

Kloks, T. Treewidth: Computations and approximations, no. 842 in Lecture Notes in Computer Science, Springer Verlag, 1994.

Časopisecká literatura podle specifikace přednášejícího. K dipozici budou též poznámky přednášejícího v angličtině.

Teaching methods -
Last update: doc. RNDr. Jiří Fiala, Ph.D. (10.10.2022)

Classic frontal teaching.

English preferred in even years, Czech in odd.

Syllabus -
Last update: FIALA/MFF.CUNI.CZ (08.04.2010)

The course will be devoted to the introduction to graph minor theory, for example we prove the Kruskal theorem on the existence of well quasiordering on finite trees. The main part of the course will be devoted to the notion of treewidth and on its relationship to graph minor theory.

Charles University | Information system of Charles University |