Název: Studium strukturálních a složitostních otázek teorie grafů
Překlad názvu: Structural and complexity questions of graph theory
Autoři: Gavenčiak, Tomáš ; Kratochvíl, Jan (vedoucí práce) ; Hliněný, Petr (oponent) ; Fomin, Fedor (oponent)
Typ dokumentu: Disertační práce
Rok: 2016
Jazyk: eng
Abstrakt: [eng] [cze]
DOCTORAL THESIS ABSTRACT Tomáš Gavenčiak Structural and complexity questions of graph theory The original cops and robber game, proposed in 1983 by Nowakowski and Winkler, and independently by Quilliot, is a two-player combinatorial pursuit game on a graph. Many related games have been introduced and studied since then, both with a purely game theoretic motivation and for their applications in graph theory and connections with graph width parameters. We give an overview of the field and present three particular results: We show bounds on the required number of cops for various connected intersection graph classes, most notably we show that on connected string graphs 15 cops always win. We show the game of cops and fast robber to be polynomially decidable on interval graphs and as a tool we generalise the problem of defensive domination and show a polynomial algorithm for interval graphs. Finally we propose and examine generalisations of tree-depth, marshals and robber games, and minors to hypergraphs and hypergraph pairs. DIZERTAČNÍ PRÁCE Tomáš Gavenčiak Studium strukturálních a složitostních otázek teorie grafů Původní hra na četníky a zloděje, kterou roku 1983 navrhli Nowakowski a Winkler, a nezávisle Quilliot, je kombinatorická pronásledovací hra na grafech. Od té doby bylo navrženo a studováno mnoho podobných a příbuzných her, a to jak s čistě teoretickou motivací, tak pro jejich aplikace v teorii grafů a souvislosti s grafovými parametry. V práci předkládáme přehled této oblasti teorie her a bližší pozornost věnujeme následujícím třem výsledkům. Ukazujeme nová omezení na počet četníků nutných k polapení zloděje v několika typech průnikových grafů; speciálně ukazujeme, že na každém souvislém průnikovém grafu křivek vyhraje už 15 četníků. Dále představujeme polynomiální algoritmus rozhodující hru na četníky a rychlého zloděje na intervalových grafech a jako nástroj zobecňujeme problém defenzivní dominance a nabízíme pro něj polynomiální algoritmus na intervalových grafech. Nakonec navrhujeme a prozkou- máváme zobecnění stromové hloubky, her na maršály a zloděje a grafových minorů na hypergrafy a hypergrafové páry.

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/79301

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


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