Parameterized Algorithms for Geometric Intersection Graphs - Agaoglu Cagirici, Deniz (2023)
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ó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ž