Thesis (Selection of subject)Thesis (Selection of subject)(version: 368)
Thesis details
   Login via CAS
Výpočetní složitost problémů kombinatorické optimalizace pro specifické třídy grafů
Thesis title in Czech: Výpočetní složitost problémů kombinatorické optimalizace pro specifické třídy grafů
Thesis title in English: Computational complexity of combinatorial problems in specific graph classes
Key words: výpočetní složitost, kombinatorika, značkovatelnost, line-grafy
English key words: computational complexity, combinatorics, labeling, line graphs
Academic year of topic announcement: 2013/2014
Thesis type: diploma thesis
Thesis language: čeština
Department: Department of Applied Mathematics (32-KAM)
Supervisor: doc. RNDr. Jiří Fiala, Ph.D.
Author: RNDr. Tomáš Masařík, Ph.D. - assigned and confirmed by the Study Dept.
Date of registration: 09.12.2013
Date of assignment: 09.12.2013
Confirmed by Study dept. on: 18.12.2013
Date and time of defence: 09.09.2014 10:00
Date of electronic submission:07.07.2014
Date of submission of printed version:31.07.2014
Date of proceeded defence: 09.09.2014
Opponents: prof. Mgr. Zdeněk Dvořák, Ph.D.
 
 
 
Guidelines
Cílem práce je určení složitosti nějakého problému z oblasti kombinatorické optimalizace, např. L(p,q) barvení pro line grafy, nebo existence lokálně podmíněných homomorfismů pro grafy nízké stromové šířky apod.
References
Reinhard Diestel: Graph Theory, Springer-Verlag (1997)

R. G. Downey, M. R. Fellows: Parameterized Complexity Springer-Verlag, 1999.

M. R. Garey, D. S. Johnson: Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman (1979)

další časopisecká literatura dle doporučení školitele
 
Charles University | Information system of Charles University | http://www.cuni.cz/UKEN-329.html