Výpočetní složitost problému váženého barvení stromů
| Thesis title in Czech: | Výpočetní složitost problému váženého barvení stromů |
|---|---|
| Thesis title in English: | Computational complexity of the weighted coloring of trees |
| Academic year of topic announcement: | 2009/2010 |
| Thesis type: | Bachelor's thesis |
| Thesis language: | |
| Department: | Department of Applied Mathematics (32-KAM) |
| Supervisor: | doc. RNDr. Jiří Fiala, Ph.D. |
| Author: | hidden - assigned and confirmed by the Study Dept. |
| Date of registration: | 27.01.2010 |
| Date of assignment: | 27.01.2010 |
| Guidelines |
| Cílem práce je prostudovat známé výsledky o váženém barvení grafů (pro vážený graf s ohodnocenými vrcholy hledáme obarvení vrcholů takové, aby součet maxim ze všech tříd byl co nejmenší). Očekává se blížší určení výpočetní resp. parameterizované složitosti na třídě stromů, popřípadě na příbuzných třídách grafů (omezeného stromového zdvihu apod.). |
| References |
| Reinhard Diestel: Graph Theory, Springer-Verlag (1997)
Andreas Brandstädt, Van Bang Le, Jeremy P. Spinrad: Graph Classes: A Survey, SIAM (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 |