Original title: Hry na grafech ve vztahu k zdvihovým parametrům grafů
Translated title: Hry na grafech ve vztahu k zdvihovým parametrům grafů
Authors: Gavenčiak, Tomáš ; Smrž, Otakar (referee) ; Kratochvíl, Jan (advisor)
Document type: Master’s theses
Year: 2009
Language: eng
Abstract: [eng] [cze]
We consider a variant of a cop and robber game with an in nitely fast robber and its relations to other similar games. We compare the helicopter game characterizing tree-width, the classical cop and robber game and its versions with various speeds of the robber. We study the complexity of the in nitely fast robber variant and give an explicit characterization of all the graphs where one cop can win. As the main result, we show a polynomial time algorithm deciding the game on interval graphs. This answers a question from the paper Fomin et al.: On tractability of Cops and Robbers game, IFIP TCS 2008, 171-185. To show the polynomiality of the game on interval graphs, we introduce a new auxiliary game on an interval representation of the graph and show the polynomiality of that game. Then we use game strategy reductions to show the equivalence of the two games. V práci se zabýváme variantou tzv. hry na četníky a zloděje s nekonečně rychlým zlodějem a jejími vztahy s ostatními podobnými hrami. Srovnáváme tzv. vrtulníkovou hru charakterizující tree-width, klasickou verzi hry na četníky a zloděje a varianty s různě rychlými zloději. U varianty s nekonečně rychlým zlodějem rozebíráme její složitost a charakterizujeme všechny grafy, kde vyhrává jeden četník. Jako hlavní výsledek ukazujeme polynomiální algoritmus rozhodující hru na intervalových grafech a zodpovídáme tak otevřenou otázku z článku Fomin a kol.: On tractability of Cops and Robbers game, IFIP TCS 2008, 171-185. V důkazu polynomiality rozhodovacího problému zavádíe novou, ekvivalentní pomocnou hru na intervalové reprezentaci grafu, o jejímž rozhodování ukážeme, že je polynomiální. Ekvivalence her je dokázána technikou redukcí herních strategií.

Institution: Charles University Faculties (theses) (web)
Document availability information: Available in the Charles University Digital Repository.
Original record: http://hdl.handle.net/20.500.11956/30592

Permalink: http://www.nusl.cz/ntk/nusl-286180


The record appears in these collections:
Universities and colleges > Public universities > Charles University > Charles University Faculties (theses)
Academic theses (ETDs) > Master’s theses