Please use this identifier to cite or link to this item: http://www.repositorio.ufc.br/handle/riufc/30194
Title in Portuguese: Jogos de perseguição em grafos e coloração localmente identificável
Title: Pursuit games on graphs and locally identifying coloring
Author: Martins, Nicolas de Almeida
Advisor(s): Sampaio, Rudini Menezes
Keywords: Lid-coloração
Jogo de polícia e ladrão
Jogo do espião
Decomposição primeval
Inaproximabilidade
Cop-number
Capture time
Issue Date: 2018
Citation: MARTINS, Nicolas de Almeida. Jogos de perseguição em grafos e coloração localmente identificável. 2018. 91 f. Tese (Doutorado em Ciência da Computação)-Universidade Federal do Ceará, Fortaleza, 2018.
Abstract in Portuguese: Nesta tese estudamos os problemas de coloração localmente identificável (lid-coloração) e diversos parâmetros relacionados a jogos de perseguição em grafos. Para colorações localmente identificáveis, mostramos que o número lid-cromático e o número lid-cromático forte são ambos O(n^(1−E))-inaproximáveis em tempo polinomial, a menos que P = NP. Também mostramos algoritmos lineares para (q, q − 4)-grafos e para grafos com largura em árvore limitada para ambos os parâmetros. Com relaçãao a jogos de perseguição, estudamos dois jogos diferentes: O Jogo de Polícia e Ladrão e o Jogo do Espião. Para o Jogo de Polícia e Ladrão mostramos valores exatos para o cop-number e o k-capture time de grafos P4-tidy e (q, q − 4)-grafos. Além disso mostramos que a famosa conjectura de Meyniel é válida para grafos P4-tidy conexos e (q, q − 4)-grafos conexos com pelo menos q vértices. Com relação ao Jogo do Espião mostramos que este problema é NP-difícil para qualquer velocidade s e qualquer distância d e, além disso, (1 − o(1)) ln n-inaproximável em tempo polinomial, a menos que P = NP. Ademais, mostramos limites para o número guardas necessários para vencer o jogo quando o mesmo transcorre em ciclos e caminhos. Provamos ainda que a versão direcionada do jogo é PSPACE-difícil para DAG’s.
Abstract: On this thesis we study the locally identifying coloring of graphs (lid-coloring) and many parameters related to pursuit games on graphs. For locally identifying colorings, we show that the lid-chromatic number and the strong lid-chromatic number are both O(n^(1−E))-inapproximable in polynomial time, unless P = NP. We also show linear algorithms for (q; q − 4)-graphs and for graphs with bounded treewidth for both parameters. Regarding pursuit games, we study two distinct games: The Cops and Robber and the Spy-Game. For the Cops and Robber game we show exact vallues for the cop-number and the k-capture time of P4-tidy graphs and (q, q − 4)-graphs. Furthermore we show that the famous Mayniel conjecture is true for P4-tidy graphs and (q, q − 4)-graphs with at least q vertices. Regarding the Spy-Game we show that it is NP-hard for any speed s and any distance d and, besides that, it is (1 − o(1)) ln n-inapproximable in polynomial time, unless P = NP. Furthermore, we show bounds to the number of guards needed to win the game when it is played on paths and cycles. We also prove that the directed version of the game is PSPACE-hard for DAG’s.
URI: http://www.repositorio.ufc.br/handle/riufc/30194
Appears in Collections:DCOMP - Teses defendidas na UFC

Files in This Item:
File Description SizeFormat 
2018_tese_namartins.pdf873,27 kBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.