Parameterized Algorithms for Geometric Intersection Graphs /
Tato práce se zabývá oblastí teorie grafů s ústředním zaměřením na parametrizovanou složitost problému izomorfismu a problému rozpoznávání na třídách $H$-grafů, které byly zavedené v roce 1992 Bir\'{o}em, Hujterem a Tuzou. $H$-grafy představují zvláštní typ reprezentace průnikových grafů a přir...
Uloženo v:
| Hlavní autor: | |
|---|---|
| Další autoři: | |
| Typ dokumentu: | VŠ práce nebo rukopis |
| Jazyk: | Angličtina |
| Vydáno: |
2023
|
| Témata: | |
| On-line přístup: | https://is.muni.cz/th/f6vsh/ |
| Shrnutí: | Tato práce se zabývá oblastí teorie grafů s ústředním zaměřením na parametrizovanou složitost problému izomorfismu a problému rozpoznávání na třídách $H$-grafů, které byly zavedené v roce 1992 Bir\'{o}em, Hujterem a Tuzou. $H$-grafy představují zvláštní typ reprezentace průnikových grafů a přirozeně zobecňují mnoho tříd grafů včetně intervalových, kruhově intervalových, split a chordálních grafů. Za použití efektivních algoritmů řešících problém automorfismu pro barvené množinové systémy a barvené systémy klik intervalových grafů a existujících algebraických grupově-teoretických rutin ukážeme, že izomorfismus $H$-grafu může být testován v čase \tt{FPT}, pokud $H$ je strom. Doplňkově podáváme plně kombinatorické \tt{FPT}-přístupy k testování izomorfismu vlastních $H$-grafů, když $H$ je strom nebo unicyklický graf. Dále uvažujeme $H$-grafy, kde $H$ je unicyklický graf. Dokážeme, že tyto $H$-grafy lze rozpoznat v čase \tt{XP} za podmínky, že jsou vstupní grafy ne-chordální, přičemž This thesis immerses itself in the landscape of graph theory, with a central focus on the parameterized complexity of the graph isomorphism and class recognition problems on $H$-graphs, introduced in 1992 by Bir\'{o}, Hujter and Tuza. $H$-graphs represent a particular type of intersection representations of graphs, and they naturally generalize many graph classes including interval, circular-arc, split and chordal graphs. By introducing efficient algorithms solving the automorphism problem for colored set families and colored clique families of interval graphs, and using existing group theoretical tools, we show that $H$-graph isomorphism can be tested in \tt{FPT}-time when $H$ is a tree. We provide complementary and fully combinatorial \tt{FPT}-approaches to test the isomorphism of proper $H$-graphs when $H$ is a tree or a unicyclic graph. We further consider $H$-graphs when $H$ is a unicyclic graph, and prove that $H$-graphs can be recognized in \tt{XP}-time when the input graph |
|---|---|
| Popis jednotky: | Vedoucí práce: Petr Hliněný |
| Fyzický popis: | 159 stran : ilustrace |