Témata prací (Výběr práce)Témata prací (Výběr práce)(verze: 368)
Detail práce
   Přihlásit přes CAS
Structural properties of graphs and eficient algorithms: Problems Between Parameters
Název práce v češtině: Strukturální vlastnosti grafů a efektivní algoritmy: Problémy separující parametry
Název v anglickém jazyce: Structural properties of graphs and eficient algorithms: Problems Between Parameters
Klíčová slova: Rozklady frafů, výpočetní složitost, parametrizovaná složitost
Klíčová slova anglicky: Graph decompositions, computational complexity, parameterized complexity
Akademický rok vypsání: 2017/2018
Typ práce: rigorózní práce
Jazyk práce: angličtina
Ústav: Katedra aplikované matematiky (32-KAM)
Vedoucí / školitel: doc. RNDr. Jiří Fiala, Ph.D.
Řešitel: skrytý - zadáno a potvrzeno stud. odd.
Datum přihlášení: 26.04.2018
Datum zadání: 26.04.2018
Datum potvrzení stud. oddělením: 26.04.2018
Datum a čas obhajoby: 28.05.2018 00:00
Datum odevzdání elektronické podoby:04.06.2018
Datum odevzdání tištěné podoby:26.05.2018
Datum proběhlé obhajoby: 28.05.2018
Zásady pro vypracování
Cílem práce je prozkoumat možná rozšířeni Courcellovy věty, tedy různé grafové rozklady, logiky prvního a druhého řádu.
Kromě obecného případu se lze zpočátku zaměřit na specifické problémy (hledání krátkýcgh cest 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
 
Univerzita Karlova | Informační systém UK