Computational and structural apects of interval graphs and their variants
| Název práce v češtině: | Výpočetní a strukturální otázky intervalových grafů a jejich variant |
|---|---|
| Název v anglickém jazyce: | Computational and structural apects of interval graphs and their variants |
| Klíčová slova: | intervalový graf, jednotkový intervalový graf, výpočetní složitost, kliková šířka, největší řez |
| Klíčová slova anglicky: | interval graph, unit interval graph, computational complexity, clique-width, maximum cut |
| 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í: | 15.03.2019 |
| Datum zadání: | 15.03.2019 |
| Datum potvrzení stud. oddělením: | 10.06.2019 |
| Datum a čas obhajoby: | 09.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: | 09.09.2019 |
| Oponenti: | doc. RNDr. Vít Jelínek, Ph.D. |
| Zásady pro vypracování |
| 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. |
| Seznam odborné literatury |
| 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) |
| Předběžná náplň práce |
| 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ží. |
| Předběžná náplň práce v anglickém jazyce |
| 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. |