Výpočetní složitost problémů kombinatorické optimalizace pro specifické třídy grafů
Název práce v češtině: | Výpočetní složitost problémů kombinatorické optimalizace pro specifické třídy grafů |
---|---|
Název v anglickém jazyce: | Computational complexity of combinatorial problems in specific graph classes |
Klíčová slova: | výpočetní složitost, kombinatorika, značkovatelnost, line-grafy |
Klíčová slova anglicky: | computational complexity, combinatorics, labeling, line graphs |
Akademický rok vypsání: | 2013/2014 |
Typ práce: | diplomová práce |
Jazyk práce: | čeština |
Ústav: | Katedra aplikované matematiky (32-KAM) |
Vedoucí / školitel: | doc. RNDr. Jiří Fiala, Ph.D. |
Řešitel: | RNDr. Tomáš Masařík, Ph.D. - zadáno a potvrzeno stud. odd. |
Datum přihlášení: | 09.12.2013 |
Datum zadání: | 09.12.2013 |
Datum potvrzení stud. oddělením: | 18.12.2013 |
Datum a čas obhajoby: | 09.09.2014 10:00 |
Datum odevzdání elektronické podoby: | 07.07.2014 |
Datum odevzdání tištěné podoby: | 31.07.2014 |
Datum proběhlé obhajoby: | 09.09.2014 |
Oponenti: | prof. Mgr. Zdeněk Dvořák, Ph.D. |
Zásady pro vypracování |
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. |
Seznam odborné literatury |
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 |