Značkování grafů a příbuzné problémy diskrétní optimalizace
| Thesis title in Czech: | Značkování grafů a příbuzné problémy diskrétní optimalizace |
|---|---|
| Thesis title in English: | Graph labeling and related problems of discrete optimization |
| Key words: | rainbow connection, L(p,q)-labeling, restricted graph classes, computational complexity, effective algorithms |
| English key words: | rainbow connection, L(p,q)-labeling, restricted graph classes, computational complexity, effective algorithms |
| Academic year of topic announcement: | 2017/2018 |
| Type of assignment: | dissertation |
| Thesis language: | |
| Department: | Department of Applied Mathematics (32-KAM) |
| Supervisor: | doc. RNDr. Jiří Fiala, Ph.D. |
| Author: |
| Guidelines |
| Cílem práce je prozkoumat výpočetní složitost problému rainbow connection a příbuzných problémů z diskrétní optimalizace, např. určení výpočetní složitosti problému L(p,q)-barvení (např. na intervalových grafech). Lze očekávat, že tyto problémy budou v obecném případě NP-těžké, proto je vhodné dále studovat jejich zúžení na specifické třídy grafů, parametrizovanou složitost, aproximovatelnost, apod. |
| References |
| I. Schiermeyer: Progress on Rainbow Connection. CTW 2010: pp 153-156, 2010.
T. Calamoneri: The L(h,k)-Labelling problem: An updated Survey and Annotated Bibliography, the Computer Journal, 54(8), pp. 1344-1371, 2011. J. Hromkovic: Algorithmics for hard problems - introduction to combinatorial optimization, randomization, approximation, and heuristics, Springer 2001 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 |