Banca de DEFESA: FELIPE CRISPIM FRAGÔSO

Uma banca de DEFESA de MESTRADO foi cadastrada pelo programa.
DISCENTE: FELIPE CRISPIM FRAGÔSO
DATA: 17/02/2020
HORA: 14:00
LOCAL: Auditório do 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: 74
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: 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 - FABIO PROTTI
Externo à Instituição - THIAGO GOUVEIA DA SILVA