Algorithmic aspects of intersection representations
| Thesis title in Czech: | Algoritmické aspekty průnikových reprezentací |
|---|---|
| Thesis title in English: | Algorithmic aspects of intersection representations |
| Key words: | průnikový graf, L-graf, rozpoznávání, NP-úplnost |
| English key words: | intersection graph, L-graph, recognition, NP-completeness |
| Academic year of topic announcement: | 2019/2020 |
| Thesis type: | Bachelor's thesis |
| Thesis language: | angličtina |
| Department: | Computer Science Institute of Charles University (32-IUUK) |
| Supervisor: | doc. RNDr. Vít Jelínek, Ph.D. |
| Author: | hidden - assigned and confirmed by the Study Dept. |
| Date of registration: | 01.11.2019 |
| Date of assignment: | 11.11.2019 |
| Confirmed by Study dept. on: | 19.11.2019 |
| Date and time of defence: | 07.07.2020 09:00 |
| Date of electronic submission: | 03.06.2020 |
| Date of submission of printed version: | 04.06.2020 |
| Date of proceeded defence: | 07.07.2020 |
| Opponents: | prof. RNDr. Jan Kratochvíl, CSc. |
| Guidelines |
| 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. |
| References |
| 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. |