Výpočetní složitost v teorii grafů
Název práce v češtině: | Výpočetní složitost v teorii grafů |
---|---|
Název v anglickém jazyce: | Computational complexity in Graph Theory |
Akademický rok vypsání: | 2005/2006 |
Typ práce: | diplomová práce |
Jazyk práce: | čeština |
Ústav: | Katedra aplikované matematiky (32-KAM) |
Vedoucí / školitel: | prof. RNDr. Jan Kratochvíl, CSc. |
Řešitel: | skrytý - zadáno a potvrzeno stud. odd. |
Datum přihlášení: | 08.11.2005 |
Datum zadání: | 08.11.2005 |
Datum a čas obhajoby: | 11.09.2006 00:00 |
Datum odevzdání elektronické podoby: | 11.09.2006 |
Datum proběhlé obhajoby: | 11.09.2006 |
Oponenti: | prof. Ing. Jan Flusser, DrSc. |
Zásady pro vypracování |
Student prostuduje literaturu týkající se výpočetní složitosti otázek souvisejících se Seidelovým switchingem a dalšími grafovými operacemi a pokusí se zodpovědět otázky složitosti switchování na grafy speciálních vlastností (např. chordální, intervalové apod.). |
Seznam odborné literatury |
M. R. Garey and D. S. Johnson. Computers and Intractability. W. H. Freeman, San Francisco, 1979
Bela Bollobas: Modern Graph Theory, Springer 1998, ISBN 0387984887 časopisecké články podle instrukcí vedoucího |