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...

Celý popis

Uloženo v:
Podrobná bibliografie
Hlavní autor: Agaoglu Cagirici, Deniz (Autor práce)
Další autoři: Hliněný, Petr, 1971- (Vedoucí práce)
Typ dokumentu: VŠ práce nebo rukopis
Jazyk:Angličtina
Vydáno: 2023
Témata:
výpočetní technika
grafové algoritmy
množiny
kombinatorika
teorie grafů
grafy funkcí
graph algorithms
sets (mathematics)
combinatorics
graph theory
computer science
graphs of functions
disertace
dissertations
On-line přístup:https://is.muni.cz/th/f6vsh/
Obálka
LEADER 04871ctm a22007097i 4500
001 MUB01006536880
003 CZ BrMU
005 20241120135851.0
008 240403s2023 xr ||||| |||||||||||eng d
STA |a POSLANO DO SKCR  |b 2024-07-15 
035 |a (ISMU-VSKP)318613 
040 |a BOD114  |b cze  |d BOD018  |e rda 
072 7 |a 517  |x Matematická analýza  |2 Konspekt  |9 13 
072 7 |a 004  |x Počítačová věda. Výpočetní technika. Informační technologie  |2 Konspekt  |9 23 
080 |a 519.17  |2 MRF 
080 |a 004  |2 MRF 
080 |a 519.178  |2 MRF 
080 |a 510.22  |2 MRF 
080 |a 519.1  |2 MRF 
080 |a 517.18(084.21)  |2 MRF 
100 1 |a Agaoglu Cagirici, Deniz  |% UČO 459192  |* [absolvent FI MU]  |4 dis 
242 1 0 |a Parameterized Algorithms for Geometric Intersection Graphs  |y eng 
245 1 0 |a Parameterized Algorithms for Geometric Intersection Graphs /  |c Deniz Agaoglu Cagirici 
264 0 |c 2023 
300 |a 159 stran :  |b ilustrace 
336 |a text  |b txt  |2 rdacontent 
337 |a bez média  |b n  |2 rdamedia 
338 |a svazek  |b nc  |2 rdacarrier 
500 |a Vedoucí práce: Petr Hliněný 
502 |a Dizertace (Ph.D.)--Masarykova univerzita, Fakulta informatiky, 2024 
520 2 |a 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ž  |% cze 
520 2 9 |a 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  |9 eng 
650 0 7 |a výpočetní technika  |7 ph137273  |2 czenas 
650 0 7 |a grafové algoritmy  |7 ph770865  |2 czenas 
650 0 7 |a množiny  |7 ph122926  |2 czenas 
650 0 7 |a kombinatorika  |7 ph121739  |2 czenas 
650 0 7 |a teorie grafů  |7 ph126555  |2 czenas 
650 0 7 |a grafy funkcí  |7 ph946128  |2 czenas 
650 0 9 |a graph algorithms  |2 eczenas 
650 0 9 |a sets (mathematics)  |2 eczenas 
650 0 9 |a combinatorics  |2 eczenas 
650 0 9 |a graph theory  |2 eczenas 
650 0 9 |a computer science  |2 eczenas 
650 0 9 |a graphs of functions  |2 eczenas 
655 7 |a disertace  |7 fd132024  |2 czenas 
655 9 |a dissertations  |2 eczenas 
658 |a Informatika  |b Fundamenty informatiky  |c FI D-INF DIFI (DIFI)  |2 CZ-BrMU 
700 1 |a Hliněný, Petr,  |d 1971-  |7 mub2013777090  |% UČO 168881  |4 ths 
710 2 |a Masarykova univerzita.  |b Katedra teorie programování  |4 dgg 
856 4 1 |u https://is.muni.cz/th/f6vsh/ 
CAT |c 20240403  |l MUB01  |h 0520 
CAT |a POSPEL  |b 02  |c 20240405  |l MUB01  |h 2123 
CAT |a POSPEL  |b 02  |c 20240405  |l MUB01  |h 2124 
CAT |a POSPEL  |b 02  |c 20240408  |l MUB01  |h 1014 
CAT |a VESELA  |b 02  |c 20240410  |l MUB01  |h 1008 
CAT |c 20240715  |l MUB01  |h 1017 
CAT |a POSPEL  |b 02  |c 20241111  |l MUB01  |h 1100 
CAT |a VESELA  |b 02  |c 20241120  |l MUB01  |h 1358 
LOW |a POSLANO DO SKCR  |b 2024-07-15 
994 - 1 |l MUB01  |l MUB01  |m VYSPR  |1 FI  |a Fakulta informatiky  |3 Doktorská práce 2023  |5 42005D2777  |8 20240410  |f 72  |f Týdenní  |r 20240410 
AVA |a INF50  |b FI  |d Doktorská práce 2023  |e available  |t K dispozici  |f 1  |g 0  |h N  |i 0 

Podobné jednotky