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ý - zadáno a potvrzeno stud. odd. |
| 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. |