Computational and structural apects of interval graphs and their variants

• Thesis title in Czech: Výpočetní a strukturální otázky intervalových grafů a jejich variant
• Thesis title in English: Computational and structural apects of interval graphs and their variants
• Key words: intervalový graf, jednotkový intervalový graf, výpočetní složitost, kliková šířka, největší řez
• English key words: interval graph, unit interval graph, computational complexity, clique-width, maximum cut
• 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: 15.03.2019
• Date of assignment: 15.03.2019
• Confirmed by Study dept. on: 10.06.2019
• Date and time of defence: 09.09.2019 09:00
• Date of electronic submission: 19.07.2019
• Date of submission of printed version: 19.07.2019
• Date of proceeded defence: 09.09.2019
• Opponents: doc. RNDr. Vít Jelínek, Ph.D.

Guidelines

Diplomant prostuduje dostupnou literaturu o intervalových grafech, zvláště UNIT intervalových grafech a jejich variantách - MIXED UNIT, SEMI MIXED UNIT intervalové grafy definované na základě množin přípustných otevřeností-uzavřeností konců intervalů v reprezentaci. Zaměří se na problémy, které jsou pro UNIT intervalové grafy jednodušší než pro všechny intervalové grafy, a posoudí, zda tyto výsledky je možno rozšířit na studované varianty.

References

M. C. Golumbic: Algorithmic Graph Theory and Perfect Graphs, Second edition, Annals of Discrete Mathematics 57, Elsevier, 2004

časopisecké publikace podle doporučení vedoucího a podle vlastní internetové rešerše,

např.

Dieter Rautenbach, Jayme Luiz Szwarcfiter: Unit Interval Graphs of Open and Closed Intervals. Journal of Graph Theory 72(4): 418-429 (2013)

Felix Joos: A Characterization of Mixed Unit Interval Graphs. Journal of Graph Theory 79(4): 267-281 (2015)

Alexandre Talon, Jan Kratochvíl: Completion of the mixed unit interval graphs hierarchy. Journal of Graph Theory 87(3): 317-332 (2018)

Preliminary scope of work

Svět průnikových reprezentací grafů skýtá fantastické možnosti vlastní vědecké práce nad zajímavými a roztomilými tématy z oblasti kombinatoriky, teorie grafů a výpočetní složistosti. Klasické téma UNIT intervalových grafů bylo v nedávné době posunuto úplnou charakterizací tříd definovaných na základě otevřenosti/uzavřenosti intervalů v reprezentaci, přičemž otázky výpočetní složitosti různých problémů zúžených na tyto třídy zatím nebyly zkoumány. Přestože si to zaslouží.

Preliminary scope of work in English

The realm of intersection defined classes of graphs offers fascinating opportunities for research in the area of combinatorics, graph theory and computational complexity. UNIT interval graphs are a classical and well studied class of graphs. This concept has been recently extended to various variants of MIXED UNIT interval graphs, based on open/closed status of the intervals in a representation. A full characterization of all such classes has been given, but questions of computational complexity of algorithmic problems restricted to these classes has not been studied yet. Though it would deserve closer attention.