Título: Jogos de Perseguição em Grafos e Coloração Localmente Identificável

Data: 22/01/2018 Horário: 14h Local: Sala de Seminários / Bloco 952

Resumo:

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-\eps)$-inaproximáveis em tempo polinomial, a menos que P=NP, bem como algoritmos lineares para (q, q-4)-grafos e para grafos com largura em árvore limitada para ambos os parâmetros. Com relação a jogos de perseguição, estudamos dois jogos diferentes: 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. 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 q2 vértices. Com relação ao Jogo do Espião mostramos que este problema é NP-difícil para qualquer velocidade do espião e qualquer distância para os guardas e, além disso, (1 − o(1)) ln ninaproximável em tempo polinomial, a menos que P = NP. Ademais, mostramos limites para um dos parâmetros do jogo quando o mesmo transcorre em ciclos e caminhos e provamos que a versão direcionada do problema é PSPACE-difícil para DAG’s.

Banca:

• Prof. Dr. Rudini Menezes Sampaio (MDCC/UFC - Orientador)
• Prof.ª Dr.ª Ana Karolinna Maia de Oliveira (MDCC/UFC)
• Prof.ª Dr.ª Ana Shirley Ferreira da Silva (UFC)
• Prof. Dr. Ronan Pardo Soares (UFC)
• Prof.ª Dr.ª Sulamita Klein (UFRJ)