Subjects

Your browser does not support JavaScript, or its support is disabled. Some features may not be available.

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

Opinion survey results Examination dates Schedule Noticeboard

Annotation -

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)

Course completion requirements -

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)

Literature - Czech

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)

Syllabus -

The course covers elements of 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 concerns to the notion of treewidth and on its relationship to graph minor theory.

The course is taught in the summer semester once every two years (alternates with NDMI077 - Algorithms for Specific Graph Classes).

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