Original title: Algoritmické aspekty průnikových reprezentací
Translated title: Algorithmic aspects of intersection representations
Authors: Chmel, Petr ; Jelínek, Vít (advisor) ; Kratochvíl, Jan (referee)
Document type: Bachelor's theses
Year: 2020
Language: eng
Abstract: [eng] [cze]
As some problems are (NP-)hard to solve in the general case, a possible approach is to try to solve the problem on a restricted class of graphs. In the thesis, we focus on graphs induced by axis-aligned L-shapes, so-called L-graphs, and a similar class of axis- aligned L-shapes and L-shapes, referred to as {L, L}-graphs, with two vertices sharing an edge if and only if their respective curves intersect. We show that recognizing both L- graphs and {L, L}-graphs is NP-complete. The second part of the thesis focuses on other typical decision problems on L-graphs and their relatives: finding the clique number, the independence number or a 3-coloring. Jelikož některé problémy jsou v obecném případě (NP-)těžké, jedním z možných pří- stupů je řešení těchto problémů na omezené třídě grafů. V této práci se zaměřujeme na grafy indukované osově zarovnanými L-tvary, tzv. L-grafy, a podobnou třídu osově zarovnaných L-tvarů a L-tvarů, tzv. {L, L}-grafy, přičemž dva vrcholy jsou spojeny hra- nou, právě když se jejich křivky protínají. Dokazujeme, že rozpoznávání jak L-grafů, tak {L, L}-grafů je NP-úplné. V druhé části práce se zaměřujeme na další obvyklé rozhodovací problémy na L-grafech a příbuzných třídách: nalezení klikovosti, 3-obarvení či nezávislosti grafu.
Keywords: intersection graph; L-graph; NP-completeness; recognition; L-graf; NP-úplnost; průnikový graf; rozpoznávání

Institution: Charles University Faculties (theses) (web)
Document availability information: Available in the Charles University Digital Repository.
Original record: http://hdl.handle.net/20.500.11956/119401

Permalink: http://www.nusl.cz/ntk/nusl-415888


The record appears in these collections:
Universities and colleges > Public universities > Charles University > Charles University Faculties (theses)
Academic theses (ETDs) > Bachelor's theses