PROGRAMA DE PÓS-GRADUAÇÃO EM INFORMÁTICA (PPGI)
UNIVERSIDADE FEDERAL DA PARAÍBA
- Telefone/Ramal
-
Não informado
Notícias
Banca de QUALIFICAÇÃO: FELIPE CRISPIM FRAGÔSO
Uma banca de QUALIFICAÇÃO de MESTRADO foi cadastrada pelo programa.
DISCENTE: FELIPE CRISPIM FRAGÔSO
DATA: 26/07/2019
HORA: 14:00
LOCAL: CENTRO DE INFORMÁTICA - CI
TÍTULO: Problema Livre de Garras: Estudo Poliédrico e Soluções Exatas
PALAVRAS-CHAVES: Problema Livre de Garra, Combinatória Poliédrica, Branch-and-Cut, Branch-and-Price.
PÁGINAS: 70
RESUMO: O grafo bipartido completo K1,3 é uma árvore denominada garra. Um grafo G é considerado Livre de Garra se não houver nenhum subgrafo induzido em G isomorfo ao grafo K1,3. O Problema Livre de Garra (PLG) é NP-Completo e consiste em encontrar o conjunto mínimo s ⊂ V (G), tal que, G - S é livre de garra. Este trabalho apresenta um estudo poliédrico do politopo associado ao PLG, explicitando sua dimensionalidade, propondo instâncias e analisando quatro algoritmos de Branch-and-Cut com inequações definidoras de facetas. Além disso, dois algoritmos Branch-and-Price são propostos e uma comparação de todos os algoritmos é feita.
MEMBROS DA BANCA:
Presidente - 2551745 - GILBERTO FARIAS DE SOUSA FILHO
Externo ao Programa - 1058696 - TEOBALDO LEITE BULHÕES JUNIOR
Externo à Instituição - THIAGO GOUVEIA DA SILVA