Algorithmic aspects of intersection-defined graph classes
| Thesis title in Czech: | Algoritmické otázky průnikových tříd grafů |
|---|---|
| Thesis title in English: | Algorithmic aspects of intersection-defined graph classes |
| Key words: | teorie grafů, průnikové třídy grafů, geometrické reprezentace, výpočetní složitost |
| English key words: | graph theory, intersection graphs, geometric representations, computational complexity |
| Academic year of topic announcement: | 2018/2019 |
| Thesis type: | diploma thesis |
| Thesis language: | angličtina |
| Department: | Department of Applied Mathematics (32-KAM) |
| Supervisor: | prof. RNDr. Jan Kratochvíl, CSc. |
| Author: | hidden - assigned and confirmed by the Study Dept. |
| Date of registration: | 20.11.2018 |
| Date of assignment: | 21.11.2018 |
| Confirmed by Study dept. on: | 10.06.2019 |
| Date and time of defence: | 04.09.2019 09:00 |
| Date of electronic submission: | 19.07.2019 |
| Date of submission of printed version: | 19.07.2019 |
| Date of proceeded defence: | 04.09.2019 |
| Opponents: | doc. RNDr. Jiří Fiala, Ph.D. |
| Guidelines |
| The student will read contemporary literature about algorithmic aspects of intersection graphs. The main goal will be to
1) learn methodology that allows exploiting the geometric representation and subsequent structural properties for design of efficient algorithms, 2) identify promising open problems in this area, and 3) try to determine the computational complexity of some of these problems. Examples of areas that should be considered may include but should not be limited to simultaneous representations, the partial representation extension problem or consideration of optimization problems restricted to generalized variants of interval graphs. |
| References |
| M. C. Golumbic: Algorithmic Graph Theory and Perfect Graphs, 2nd
Edition, North Holland 2004, ISBN 9780444515308 J. Spinrad: Efficient Graph Representations, AMS 2003 conference and journal articles upon recommendation of the advisor |