Defesa de Tese: Thiago Braga Marcilon

Título: Resultados no Tempo Máximo e no Número de Envoltória nas Convexidades P3 e Geodésica.

Data: 16/02/2017 Horário: 14h Local: Sala de Seminários do Bloco 952 - Campus do Pici

Resumo:

Convexidade em grafos é um conceito inspirado na convexidade da geometria euclidiana e vem sendo bastante explorado nas últimas décadas. Muitas aplicações reais como a difusão de uma infecção ou de informação em uma rede social podem ser modeladas usando alguma convexidade em grafos baseada em caminhos do grafo. Nesta tese, nós abordamos dois problemas computacionais relacionados à convexidade em grafos: Número de Envoltória e Tempo Máximo de Infecção. Fixada uma convexidade C, o problema Número de Envoltória consiste em, dados um grafo G e inteiro k, determinar se o número de envoltória de G na convexidade C é no máximo k. O problema Tempo Máximo de Infecção consiste em, dados um grafo G e inteiro k, determinar se o tempo máximo de infecção de G na convexidade C é no mínimo k. Apresentamos algoritmos polinomiais para o problema Tempo Máximo de Infecção na convexidade P3 em algumas classes de grafos e para k fixo. Apresentamos também algoritmos tratáveis em parâmetro fixo na combinação dos parâmetros grau máximo do grafo e k e na combinação dos parâmetros largura em árvore do grafo e k. Também apresentamos resultados de NP-completude para o problema Tempo Máximo de Infecção na convexidade P3 em algumas classes de grafos e para algumas restrições da entrada k. Apresentamos ainda a sua W[1]-dificuldade para o parâmetro largura em árvore. Finalmente, mostramos que o problema Número de Envoltória na convexidade P3 é W[1]-difícil no parâmetro k em grafos livres de K3 com grau máximo seis. Mostramos também que o problema Número de Envoltória na convexidade geodésica é W[1]-difícil no parâmetro k em grafos com diâmetro dois e na combinação dos parâmetros largura em árvore e k. Apresentamos ainda um algoritmo XP no parâmetro largura em árvore que calcula o número de envoltória de um grafo na convexidade geodésica.

Banca:

  • Prof. Dr. Rudini Menezes Sampaio (MDCC/UFC - Orientador)
  • Prof. Dr. Ignasi Sau Valls (LIRMM)
  • Prof. Dr. Jayme Luiz Szwarcfiter (UFRJ)
  • Prof. Dr. Uéverton dos Santos Souza (UFF)
  • Prof. Dr. Júlio César Silva Araújo (UFC)
  • Prof.ª Dr.ª Cláudia Linhares Sales (MDCC/UFC)