Logo ČVUT
CZECH TECHNICAL UNIVERSITY IN PRAGUE
STUDY PLANS
2018/2019

Graph Theory

Login to KOS for course enrollment Display time-table
Code Completion Credits Range
PI-TGR ZK 4 2+1
Lecturer:
Ondřej Suchý (guarantor), Tomáš Valla
Tutor:
Jan Kratochvíl (guarantor), Ondřej Suchý (guarantor), Tomáš Valla
Supervisor:
Department of Theoretical Computer Science
Synopsis:

Attention will be paid both to structural issues and to questions of algorithmization and computational complexity of basic optimization problems restricted to special graph classes, aiming at determining the boundary between polynomially solvable and NP-hard variants of the problems.

Requirements:

General knowledge of discrete mathematics and efficient algorithms.

Syllabus of lectures:

1. Network Flows

2. Applications of network flows - higher connectivity of graphs, Ford-Fulkerson and Menger Theorem, Hall's Marriage Theorem

3. Matching in graphs

4. Planar graphs - Kuratowski Theorem, 5 Color Theorem

5. Chromatic number and colorings of graphs

6. Hamiltonian graphs

7. Minors and their algorithmic usage

8. Dynamic programming on trees and grids, path and tree decompositions and basic properties

9. Dynamic programming on tree decompositions

10. MSOL, Courcelle Theorem and an alternative characterization of tree width

11. Computing tree width, tree width of planar graphs and algorithms for planar graphs, bidimensionality

12. Baker's shifitng technique, decopositions of dense graphs

Syllabus of tutorials:
Study Objective:

Overview of modern methods of graph theory.

Study materials:

1. R. Diestel, Graph Theory, 5th edition, Springer, 2017.

2. Marek Cygan, Fedor V. Fomin, Łukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk, Saket Saurabh, Parameterized Algorithms, Springer 2015.

3. Downey, Rodney G., Fellows, Michael R.: Fundamentals of Parameterized Complexity, Springer, 2013.

Note:
Further information:
https://courses.fit.cvut.cz/PI-TGR/
Time-table for winter semester 2018/2019:
Time-table is not available yet
Time-table for summer semester 2018/2019:
Time-table is not available yet
The course is a part of the following study plans:
Data valid to 2019-05-19
For updated information see http://bilakniha.cvut.cz/en/predmet1602206.html