Výpočetní složitost problému váženého barvení stromů
| Název práce v češtině: | Výpočetní složitost problému váženého barvení stromů |
|---|---|
| Název v anglickém jazyce: | Computational complexity of the weighted coloring of trees |
| Akademický rok vypsání: | 2009/2010 |
| Typ práce: | bakalářská práce |
| Jazyk práce: | |
| Ú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í: | 27.01.2010 |
| Datum zadání: | 27.01.2010 |
| Zásady pro vypracování |
| 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.). |
| Seznam odborné literatury |
| 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 |