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. |