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