Algoritmické problémy související s průnikovými grafy
Název práce v češtině: | Algoritmické problémy související s průnikovými grafy |
---|---|
Název v anglickém jazyce: | Algorithmic problems related to the intersection graphs |
Klíčová slova: | průnikové grafy, k-bendy, klikové pokrytí, složitost, aproximační algoritmy |
Klíčová slova anglicky: | intersection graphs, k-bends, clique covers, computational complexity, approximation algorithms |
Akademický rok vypsání: | 2012/2013 |
Typ práce: | diplomová práce |
Jazyk práce: | angličtina |
Ústav: | Katedra softwaru a výuky informatiky (32-KSVI) |
Vedoucí / školitel: | RNDr. Martin Pergel, Ph.D. |
Řešitel: | skrytý![]() |
Datum přihlášení: | 11.09.2012 |
Datum zadání: | 11.09.2012 |
Datum potvrzení stud. oddělením: | 19.09.2012 |
Datum a čas obhajoby: | 29.05.2013 00:00 |
Datum odevzdání elektronické podoby: | 11.04.2013 |
Datum odevzdání tištěné podoby: | 12.04.2013 |
Datum proběhlé obhajoby: | 29.05.2013 |
Oponenti: | Mgr. Pavel Rytíř, Ph.D. |
Zásady pro vypracování |
Uchazeč nastuduje dostupnou literaturu, seznámí se s dosavadními výsledky v oboru a pokusí se je vylepšit, případně navrhne nové problémy ke zkoumání. Problémy by se měly týkat především průnikových grafů a jejich algoritmických vlastností. |
Seznam odborné literatury |
Michael R. Garey, David S. Johnson: Computers and intractability: a guide to the theory of NP-completeness. New York: W. H. Freeman and Company 1979, ISBN 0-7167-1045-5
Jeremy P. Spinrad: Efficient graph representations, AMS 2003, ISBN-13 978-0-8218-2815-1 Vijay V. Vazirani: Approximation algorithms, Springer 2003, ISBN 3-540-65367-8 Andreas Brandstädt, Van Bang Le, Jeremy P. Spinrad: Graph Classes: A Survey, SIAM, 1987, ISBN-13 9780898714326 dostupná časopisecká literatura dle vlastního uvážení a pokynů vedoucího. |