Název: Grupy symetrií grafů
Překlad názvu: Groups of automorphisms of graphs
Autoři: Zeman, Peter ; Nedela, Roman (vedoucí práce) ; Felsner, Stefan (oponent) ; Širáň, Jozef (oponent)
Typ dokumentu: Disertační práce
Rok: 2022
Jazyk: eng
Abstrakt: [eng] [cze]
Groups of automorphisms of graphs - abstract In this thesis we investigate automorphism groups of several restricted classes of graphs from structural and computational point of view. For interval, permutation, circle, and planar graphs we give inductive characterizations of their automorphism groups in terms of group products. For chordal graphs of bounded leafage, prove that computing the automorphism group, and consequently the isomorphism problem, is fixed parameter tractable. For maps on surfaces, we give a linear time algorithm computing the automor- phism group, parametrized by the genus of the underlying surface. 1 Groups of automorphisms of graphs - abstrakt V tejto práci skúmame grupy automorfizmov špecifických tried grafov z štrukturál- neho a výpočetného hladiska. Pre intervalové, permutačné, tetivové a rovinné grafy sme odvodili induktívnu charakterizáciu grúp automorfizmov pomocou grupových súčinov. Pre chordálne grafy s ohraničenou listnatosťou sme dokázali, že problémy výpočtu grupy automorfizmov a testovania izomorfizmu sú fixed parameter tractable. Pre mapy na plochách sme popísali lineárny algoritmus, ktorý počíta grupu automorfizmov mapy na ploche s pevným rodom. 1
Klíčová slova: Graf|grupa|automorfizmus|algoritmus|složitost; Graph|group|automorphism|algorithm|complexity

Instituce: Fakulty UK (VŠKP) (web)
Informace o dostupnosti dokumentu: Dostupné v digitálním repozitáři UK.
Původní záznam: http://hdl.handle.net/20.500.11956/173835

Trvalý odkaz NUŠL: http://www.nusl.cz/ntk/nusl-506915


Záznam je zařazen do těchto sbírek:
Školství > Veřejné vysoké školy > Univerzita Karlova > Fakulty UK (VŠKP)
Vysokoškolské kvalifikační práce > Disertační práce