Algorithmic aspects of intersection representations
| Název práce v češtině: | Algoritmické aspekty průnikových reprezentací |
|---|---|
| Název v anglickém jazyce: | Algorithmic aspects of intersection representations |
| Klíčová slova: | průnikový graf, L-graf, rozpoznávání, NP-úplnost |
| Klíčová slova anglicky: | intersection graph, L-graph, recognition, NP-completeness |
| Akademický rok vypsání: | 2019/2020 |
| Typ práce: | bakalářská práce |
| Jazyk práce: | angličtina |
| Ústav: | Informatický ústav Univerzity Karlovy (32-IUUK) |
| Vedoucí / školitel: | doc. RNDr. Vít Jelínek, Ph.D. |
| Řešitel: | skrytý - zadáno a potvrzeno stud. odd. |
| Datum přihlášení: | 01.11.2019 |
| Datum zadání: | 11.11.2019 |
| Datum potvrzení stud. oddělením: | 19.11.2019 |
| Datum a čas obhajoby: | 07.07.2020 09:00 |
| Datum odevzdání elektronické podoby: | 03.06.2020 |
| Datum odevzdání tištěné podoby: | 04.06.2020 |
| Datum proběhlé obhajoby: | 07.07.2020 |
| Oponenti: | prof. RNDr. Jan Kratochvíl, CSc. |
| Zásady pro vypracování |
| Cílem práce je získat nové vědecké výsledky týkající se grafových tříd definovaných pomocí existence vhodné průnikové reprezentace. Zkoumání se zaměří zejména na tzv. L-grafy a další příbuzné třídy grafů, jako např. vnějškové L-grafy, B_k-VPG grafy apod. Cílem práce bude zkoumat algoritmickou složitost jednak pro problém rozpoznávání grafů v těchto třídách, jednak pro problém určení hodnot základních grafových parametrů, jako je např. klikovost, nezávislost, barevnost nebo velikost nejmenší dominující množiny. |
| Seznam odborné literatury |
| Steven Chaplick, Vít Jelínek, Jan Kratochvíl, and Tomáš Vyskočil: Bend-bounded path intersection graphs: Sausages, noodles, and waffles on a grill. In proceedings of the 38th International
Workshop on Graph-Theoretic Concepts in Computer Science (WG 2012), Jerusalem, Israel, 274-285, 2012. Stefan Felsner, Kolja B. Knauer, George B. Mertzios, and Torsten Ueckerdt: Intersection graphs of L-shapes and segments in the plane, Discrete Applied Mathematics, 206:48-55, 2016. J. Mark Keil, Joseph S. B. Mitchell, Dinabandhu Pradhan, and Martin Vatshelle: An algorithm for the maximum weight independent set problem on outerstring graphs, Comput. Geom., 60:19-25, 2017. Saeed Mehrabi: Approximation algorithms for independence and domination on B1-VPG and B1-EPG graphs, arxiv:1702.05633, 2017. |