Partial representation extension for subclasses of interval graphs
| Název práce v češtině: | Rozšiřování částečných reprezentací podtříd intervalových grafů |
|---|---|
| Název v anglickém jazyce: | Partial representation extension for subclasses of interval graphs |
| Klíčová slova: | graf|intervalový graf|výpočetní složitost|částečná reprezentace |
| Klíčová slova anglicky: | graph|interval graph|computational complexity|partial representation |
| Akademický rok vypsání: | 2020/2021 |
| 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í: | 14.04.2021 |
| Datum zadání: | 14.04.2021 |
| Datum potvrzení stud. oddělením: | 18.05.2021 |
| Datum a čas obhajoby: | 23.06.2021 09:00 |
| Datum odevzdání elektronické podoby: | 21.05.2021 |
| Datum odevzdání tištěné podoby: | 21.05.2021 |
| Datum proběhlé obhajoby: | 23.06.2021 |
| Oponenti: | doc. RNDr. Vít Jelínek, Ph.D. |
| Zásady pro vypracování |
| The student will study the existing literature on subclasses of interval graphs and on the computational complexity of extending partial representations. The goal is to explore if the existing algorithms for PROPER and UNIT interval graphs can be generalized to classes of mixed unit interval graphs. |
| Seznam odborné literatury |
| M.C. Dourado, V.B. Le, F. Protti, D. Rautenbach and J.L. Szwarcfiter, Mixed unit interval graphs, Discrete Math. 312, 3357-3363 (2012)
D. Rautenbach and J.L. Szwarcfiter, Unit Interval Graphs of Open and Closed Intervals, J. Graph Theory 72(4), 418-429 (2013) F. Joos, A characterization of mixed unit interval graphs, J. Graph Theory 79(4): 267-281 (2015) P. Klavík, J. Kratochvíl, Y. Otachi, T. Saitoh, T. Vyskocil: Extending Partial Representations of Interval Graphs, Algorithmica 78(3): 945-967 (2017) P. Klavík, J. Kratochvíl, Y. Otachi, I. Rutter, T. Saitoh, M. Saumell, T. Vyskocil: Extending Partial Representations of Proper and Unit Interval Graphs, Algorithmica 77(4): 1071-1104 (2017) A. Talon, J. Kratochvíl: Completion of the mixed unit interval graphs hierarchy, J. Graph Theory 87(3): 317-332 (2018) |