Partial representation extension for subclasses of interval graphs
| Thesis title in Czech: | Rozšiřování částečných reprezentací podtříd intervalových grafů |
|---|---|
| Thesis title in English: | Partial representation extension for subclasses of interval graphs |
| Key words: | graf|intervalový graf|výpočetní složitost|částečná reprezentace |
| English key words: | graph|interval graph|computational complexity|partial representation |
| Academic year of topic announcement: | 2020/2021 |
| 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: | 14.04.2021 |
| Date of assignment: | 14.04.2021 |
| Confirmed by Study dept. on: | 18.05.2021 |
| Date and time of defence: | 23.06.2021 09:00 |
| Date of electronic submission: | 21.05.2021 |
| Date of submission of printed version: | 21.05.2021 |
| Date of proceeded defence: | 23.06.2021 |
| Opponents: | doc. RNDr. Vít Jelínek, Ph.D. |
| Guidelines |
| 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. |
| References |
| 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) |