Please use this identifier to cite or link to this item: https://repositorio.ufpb.br/jspui/handle/123456789/15578
metadata.dc.type: TCC
Title: Um algoritmo de planos de corte para o problema livre de garra: estudo poliédrico e implementação Branch-and-Cut
metadata.dc.creator: Fragoso, Felipe Crispim
metadata.dc.contributor.advisor1: Farias, Gilberto
metadata.dc.description.resumo: Seja G = (V;E) um grafo, no qual V e o conjunto de vertices e E o conjunto de arestas. Um grafo garra é de nido como sendo um grafo bipartido completo K1,3. O Problema Livre de Garra (PLG) tem como objetivo encontrar um subconjunto minimo de vértices S c V de modo que nenhum subgrafo induzido por vértice em G[V / S] seja um grafo garra. O presente trabalho realiza um estudo poliedral para o PLG, que é um problema NP-completo, apresentando dois modelos de programa c~ao linear inteira (Fg e FSk ), sendo o ultimo implementado por meio de um procedimento baseado em planos de corte. Experimentos computacionais foram realizados em instâncias com diversas densidades e contendo até 100 vértices. Os resultados obtidos sugerem que FSk teve desempenho superior quando comparado a Fg.
Abstract: Let G = (V;E) be a simple graph, where V is the set of vertices and E is the set of edges. A claw is de ned as a complete bipartite graph K1,3. The Claw-free problem (CFP) aims at nding a minimum subset of vertices S c V such that none of the vertex-induced subgraphs of G[V n S] are claws. The present work performs a polyhedral study on the CFP, which is a NP-complete problem, presenting 2 integer programming models(Fg and FSk ), where FSk is implemented with a cutting plane-based procedure. Computational experiments were performed in instances with di erent densities with up to 100 vertices. The results obtained suggest that FSk had a superior performance when compared to Fg.
Keywords: Algoritmo
Problema livre de garra
Plano de cortes
Combinatória poliédrica
metadata.dc.subject.cnpq: CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO
metadata.dc.language: por
metadata.dc.publisher.country: Brasil
Publisher: Universidade Federal da Paraíba
metadata.dc.publisher.initials: UFPB
metadata.dc.publisher.department: Informática
metadata.dc.rights: Acesso Aberto
Attribution 3.0 Brazil
metadata.dc.rights.uri: http://creativecommons.org/licenses/by/3.0/br/
URI: https://repositorio.ufpb.br/jspui/handle/123456789/15578
Issue Date: 13-Jun-2017
Appears in Collections:TCC - Ciência da Computação - CI

Files in This Item:
File Description SizeFormat 
FCF19072017.pdf2,08 MBAdobe PDFView/Open


This item is licensed under a Creative Commons License Creative Commons