Jogos de perseguição em grafos e coloração localmente identificável

Detalhes bibliográficos
Ano de defesa: 2018
Autor(a) principal: Martins, Nicolas de Almeida
Orientador(a): Não Informado pela instituição
Banca de defesa: Não Informado pela instituição
Tipo de documento: Tese
Tipo de acesso: Acesso aberto
Idioma: por
Instituição de defesa: Não Informado pela instituição
Programa de Pós-Graduação: Não Informado pela instituição
Departamento: Não Informado pela instituição
País: Não Informado pela instituição
Palavras-chave em Português:
Link de acesso: http://www.repositorio.ufc.br/handle/riufc/30194
Resumo: 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.