Algorithmic aspects of intersection-defined graph classes
| Název práce v češtině: | Algoritmické otázky průnikových tříd grafů |
|---|---|
| Název v anglickém jazyce: | Algorithmic aspects of intersection-defined graph classes |
| Klíčová slova: | teorie grafů, průnikové třídy grafů, geometrické reprezentace, výpočetní složitost |
| Klíčová slova anglicky: | graph theory, intersection graphs, geometric representations, computational complexity |
| Akademický rok vypsání: | 2018/2019 |
| Typ práce: | diplomová práce |
| Jazyk práce: | anglič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í: | 20.11.2018 |
| Datum zadání: | 21.11.2018 |
| Datum potvrzení stud. oddělením: | 10.06.2019 |
| Datum a čas obhajoby: | 04.09.2019 09:00 |
| Datum odevzdání elektronické podoby: | 19.07.2019 |
| Datum odevzdání tištěné podoby: | 19.07.2019 |
| Datum proběhlé obhajoby: | 04.09.2019 |
| Oponenti: | doc. RNDr. Jiří Fiala, Ph.D. |
| Zásady pro vypracování |
| 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. |
| Seznam odborné literatury |
| 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 |