Banca de QUALIFICAÇÃO: JOSÉ FAGNER RODRIGUES MEDEIROS

Uma banca de QUALIFICAÇÃO de MESTRADO foi cadastrada pelo programa.
DISCENTE: JOSÉ FAGNER RODRIGUES MEDEIROS
DATA: 26/07/2019
HORA: 15:30
LOCAL: CENTRO DE INFORMÁTICA - CI
TÍTULO: Estratégias de resolução exata para o problema do corte global rotulado mínimo
PALAVRAS-CHAVES: grafo rotulado, fecho cromático, corte global rotulado mínimo
PÁGINAS: 40
RESUMO: 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 Problema do Corte Global Rotulado Mínimo (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. Com base no modelo PART2 de Silva et al. (2016) propomos novas estratégias de resolução exata para o PCGRM, que chamamos de MFd. Este modelo apresenta um novo conceito para os grafos coloridos, o fecho cromático, permitindo assim, a criação de novos algoritmos de separação das novas restrições propsotas a serem adicionadas a estratégia de branch-and-cut adotada. Os experimentos computacionais demonstraram que o novo modelo proposto obteve uma grande melhoria de tempo em relação ao modelo anterior.
MEMBROS DA BANCA:
Presidente - 2551745 - GILBERTO FARIAS DE SOUSA FILHO
Interno - 1175878 - LUCIDIO DOS ANJOS FORMIGA CABRAL
Externo à Instituição - THIAGO GOUVEIA DA SILVA