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 2024
• 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
• Guarantor: doc. RNDr. Jiří Fiala, Ph.D.
• Class: Informatika Mgr. - Diskrétní modely a algoritmy
• Classification: Informatics > Discrete Mathematics

Annotation

English

Special course for advanced undergraduate and graduate students devoted to graph minor theory in its relationship to treewidth.

Last update: FIALA/MFF.CUNI.CZ (08.10.2008)

Czech

Kurz zaměřený na teorii grafových minorů a zvláště na aplikace souvisejícího pojmu stromového zdvihu pro návrh algoritmů. Vhodné pro studenty mat. a inf. od 3.r. i pro doktorandy (M a I).

Last update: T_KAM (15.05.2003)

Course completion requirements

English

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

Last update: Fiala Jiří, doc. RNDr., Ph.D. (07.10.2019)

Czech

Osvojení látky v rozsahu syllabu a schopnost je aplikovat na úlohy z oboru.

Last update: Fiala Jiří, doc. RNDr., Ph.D. (12.10.2017)

Literature

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ě.

Last update: FIALA (15.03.2006)

Teaching methods

English

Classic frontal teaching.

English preferred in even years, Czech in odd.

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

Czech

Klasická frontální výuka.

V lichých letech preferovaně česky, v sudých anglicky.

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

Syllabus

English

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.

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

Czech

Na kurzu bude probrán úvod do teorie grafových minorů a dobrých kvaziuspořádání, m.j. bude dokázána Kruskalova věta o dobrém kvaziuspořádání na třídě konečných stromů. Těžiště kurzu je založeno na pojmu stromového zdvihu a na jeho vztahu k teorii grafových minorů.

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