|
| |
|
|
Hry na grafech ve vztahu k zdvihovým parametrům grafů
Gavenčiak, Tomáš ; Smrž, Otakar (referee) ; Kratochvíl, Jan (advisor)
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.
|
|
|
On-line algorithms for bipartite graph coloring
Chludil, Josef ; Gavenčiak, Tomáš (referee) ; Pangrác, Ondřej (advisor)
Instance of the on-line graph coloring problem is a graph together with a permutation of its vertices (viewed as a linear ordering of the vertex set). The goal is to color the graph with vertices taken in the given order using the information of the subgraph induced by previous vertices. The most natural algorithm is the First Fit algorithm using in each step the first possible color. Unfortunately optimum number of colors can be linear dependent on number of vertices of graph even for bipartite graphs. On the other hand, there is an algorithm with logarithmic approximation factor for this class of graphs.
|
|
|
Hry na grafech
Gavenčiak, Tomáš ; Kratochvíl, Jan (advisor) ; Pergel, Martin (referee)
In this thesis we study properties of one cop&robber game. In this game two players (Cop and Robber) take turns in moving on a finite undirected graph. Both players move with the speed at most one edge per turn. They both know the complete game status. If at any time Cop shares a vertex with Robber, Cop wins. If that never happens, Robber wins. Games of this type are important as models of searching in graphs and networks and for the connection to the width parameters of graphs. We closely examine the class of graphs with a winning strategy for Cop (the so called cop-win graphs) and construct best strategies for both Cop and Robber. The previously known results include the fact that the number of moves in which Cop can catch Robber on every cop-win graph on n vertices is bounded by n3 and there are graphs which require n 4. We show that this number is exactly n 4.
|
guest ::
