PROGRAMA DE PÓS-GRADUAÇÃO EM INFORMÁTICA (PPGI)
UNIVERSIDADE FEDERAL DA PARAÍBA
- Telefone/Ramal
-
Não informado
Notícias
Banca de DEFESA: JOSÉ FAGNER RODRIGUES MEDEIROS
Uma banca de DEFESA de MESTRADO foi cadastrada pelo programa.
DISCENTE: JOSÉ FAGNER RODRIGUES MEDEIROS
DATA: 06/07/2020
HORA: 14:00
LOCAL: Defesa remota (Google Meet)
TÍTULO: Estratégias de resolução exata para o problema do corte global rotulado mínimo
PALAVRAS-CHAVES: grafos com arestas rotuladas, branch-and-cut, conectividade
PÁGINAS: 50
GRANDE ÁREA: Ciências Exatas e da Terra
ÁREA: Ciência da Computação
SUBÁREA: Teoria da Computação
ESPECIALIDADE: Computabilidade e Modelos de Computação
RESUMO: Neste trabalho, abordamos o Problema do Corte Global Rotulado Míınimo (PCG-RM), que é um problema de análise combinatória e pode ser definido formalmente como: seja G= (V,E,L) um grafo com arestas rotuladas, no qual V é o conjunto de vértices de G, E é o conjunto de arestas, L ́é o conjunto de rótulos (cores) sobre E e cada aresta e∈E possui um rótulo L(e) associado; o PCGRM tem como objetivo encontrar um subconjunto de rótulos L′ ⊆ L de modo que o grafo G= (V,E′,L\L′) seja desconexo e |L′| seja minimizado. Então, com o objetivo de solucionar este problema, desenvolvemos algumas estratégias de resolução exata, estendemos e adaptamos os conceitos de fecho cromático, e desenvolvemos uma nova família de formulações matemáticas chamada MFd. Para construção do MFd, tivemos como base um modelo presente na literatura chamado PART2, que é definido em Silva et al (2016). Os experimentos computacionais demonstraram que o modelo proposto neste trabalho obteve uma grande melhoria de tempo em relação ao modelo PART2.
MEMBROS DA BANCA:
Presidente - 2551745 - GILBERTO FARIAS DE SOUSA FILHO
Interno - 1175878 - LUCIDIO DOS ANJOS FORMIGA CABRAL
Externo ao Programa - 1058696 - TEOBALDO LEITE BULHÕES JUNIOR
Externo à Instituição - THIAGO GOUVEIA DA SILVA