Defesa de Qualificação de Doutorado: Gabriel Hellen de Sousa
Data da publicação: 27 de janeiro de 2025 Categoria: Notícias, Qualificação de Doutorado
Título: Programação Matemática em problemas de convexidade em grafos: Número de Envoltória, Convexidade e Intervalo
Data: 03/02/2025
Horário: 10h
Local: Sala de Seminários – Bloco 952
Resumo:
Seja G=(V,E) um grafo simples e não orientado. O número de envoltória de G refere-se ao menor número de vértices que, inicialmente contaminados, são capazes de, de forma iterativa, contaminar todos os vértices do grafo. Quando o processo de infecção é restrito a uma única iteração, esse parâmetro é denominado número de intervalo. O número de convexidade corresponde à cardinalidade do maior subconjunto próprio de vértices infectados que não podem provocar novas infecções, caracterizando um conjunto convexo. Determinar cada um desses três parâmetros é um problema reconhecidamente NP-difícil. Nesta qualificação, abordamos esses parâmetros por meio de formulações matemáticas e métodos heurísticos. Apresentamos uma revisão bibliográfica sobre os artigos da literatura relacionados a formulações e heurísticas que tratam desses três parâmetros e propomos nossas contribuições iniciais para o campo, introduzindo novas heurísticas e formulações matemáticas. Além disso, propomos um estudo inicial sobre o politopo associado a essas formulações.
Banca examinadora:
- Prof. Dr. Manoel Bezerra Campêlo Neto (MDCC/UFC) – Orientador
- Prof. Dr. Júlio César Silva Araújo (MDCC/UFC)
- Prof. Dr. Rafael Castro de Andrade (MDCC/UFC)
