velikost textu

Structural and complexity questions of graph theory

Upozornění: Informace získané z popisných dat či souborů uložených v Repozitáři závěrečných prací nemohou být použity k výdělečným účelům nebo vydávány za studijní, vědeckou nebo jinou tvůrčí činnost jiné osoby než autora.
Název:
Structural and complexity questions of graph theory
Název v češtině:
Studium strukturálních a složitostních otázek teorie grafů
Typ:
Disertační práce
Autor:
Mgr. Tomáš Gavenčiak
Školitel:
prof. RNDr. Jan Kratochvíl, CSc.
Oponenti:
doc. RNDr. Petr Hliněný
prof. Fedor Fomin
Id práce:
70457
Fakulta:
Matematicko-fyzikální fakulta (MFF)
Pracoviště:
Katedra aplikované matematiky (32-KAM)
Program studia:
Informatika (P1801)
Obor studia:
Diskrétní modely a algoritmy (4I4)
Přidělovaný titul:
Ph.D.
Datum obhajoby:
2. 6. 2016
Výsledek obhajoby:
Prospěl/a
Jazyk práce:
Angličtina
Abstrakt:
ABSTRAKT 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.
Abstract v angličtině:
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.
Dokumenty
Stáhnout Dokument Autor Typ Velikost
Stáhnout Text práce Mgr. Tomáš Gavenčiak 1.08 MB
Stáhnout Abstrakt v českém jazyce Mgr. Tomáš Gavenčiak 25 kB
Stáhnout Abstrakt anglicky Mgr. Tomáš Gavenčiak 21 kB
Stáhnout Posudek vedoucího prof. RNDr. Jan Kratochvíl, CSc. 286 kB
Stáhnout Posudek oponenta doc. RNDr. Petr Hliněný 99 kB
Stáhnout Posudek oponenta prof. Fedor Fomin 142 kB
Stáhnout Záznam o průběhu obhajoby 420 kB