Algoritmické problémy související s průnikovými grafy
| Thesis title in Czech: | Algoritmické problémy související s průnikovými grafy |
|---|---|
| Thesis title in English: | Algorithmic problems related to the intersection graphs |
| Key words: | průnikové grafy, k-bendy, klikové pokrytí, složitost, aproximační algoritmy |
| English key words: | intersection graphs, k-bends, clique covers, computational complexity, approximation algorithms |
| Academic year of topic announcement: | 2012/2013 |
| Thesis type: | diploma thesis |
| Thesis language: | angličtina |
| Department: | Department of Software and Computer Science Education (32-KSVI) |
| Supervisor: | RNDr. Martin Pergel, Ph.D. |
| Author: | hidden - assigned and confirmed by the Study Dept. |
| Date of registration: | 11.09.2012 |
| Date of assignment: | 11.09.2012 |
| Confirmed by Study dept. on: | 19.09.2012 |
| Date and time of defence: | 29.05.2013 00:00 |
| Date of electronic submission: | 11.04.2013 |
| Date of submission of printed version: | 12.04.2013 |
| Date of proceeded defence: | 29.05.2013 |
| Opponents: | Mgr. Pavel Rytíř, Ph.D. |
| Guidelines |
| 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í. |
| References |
| 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. |