Skip navigation
DSpace logo

  1. Repositório Institucional da UFPB
  2. UFPB - Campus I - Centro de Informática (CI)
  3. CI - Trabalhos de Conclusão de Curso de Graduação
  4. TCC - Ciência da Computação - CI
Use este identificador para citar ou linkar para este item: https://repositorio.ufpb.br/jspui/handle/123456789/15578
Registro completo de metadados
Campo DCValorIdioma
dc.creatorFragoso, Felipe Crispim-
dc.date.accessioned2019-09-06T14:30:42Z-
dc.date.available2017-07-19-
dc.date.available2019-09-06T14:30:42Z-
dc.date.issued2017-06-13-
dc.identifier.urihttps://repositorio.ufpb.br/jspui/handle/123456789/15578-
dc.description.abstractLet 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.pt_BR
dc.description.provenanceSubmitted by Rogerio Marques (rogerioferreiramarques1@gmail.com) on 2019-09-06T14:30:42Z No. of bitstreams: 2 license_rdf: 914 bytes, checksum: 4d2950bda3d176f570a9f8b328dfbbef (MD5) FCF19072017.pdf: 2125856 bytes, checksum: 3d9cdc301a81fbf149cc6ca1e7840c51 (MD5)en
dc.description.provenanceMade available in DSpace on 2019-09-06T14:30:42Z (GMT). No. of bitstreams: 2 license_rdf: 914 bytes, checksum: 4d2950bda3d176f570a9f8b328dfbbef (MD5) FCF19072017.pdf: 2125856 bytes, checksum: 3d9cdc301a81fbf149cc6ca1e7840c51 (MD5) Previous issue date: 2017-06-13en
dc.description.sponsorshipNenhumapt_BR
dc.languageporpt_BR
dc.publisherUniversidade Federal da Paraíbapt_BR
dc.rightsAcesso abertopt_BR
dc.rightsAttribution 3.0 Brazil*
dc.rights.urihttp://creativecommons.org/licenses/by/3.0/br/*
dc.subjectAlgoritmopt_BR
dc.subjectProblema livre de garrapt_BR
dc.subjectPlano de cortespt_BR
dc.subjectCombinatória poliédricapt_BR
dc.titleUm algoritmo de planos de corte para o problema livre de garra: estudo poliédrico e implementação Branch-and-Cutpt_BR
dc.typeTCCpt_BR
dc.contributor.advisor1Farias, Gilberto-
dc.creator.Latteshttp://buscatextual.cnpq.br/buscatextual/visualizacv.do?id=K4368514J3pt_BR
dc.creator.Latteshttp://buscatextual.cnpq.br/buscatextual/visualizacv.do?id=K4368514J3pt_BR
dc.description.resumoSeja 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.pt_BR
dc.publisher.countryBrasilpt_BR
dc.publisher.departmentInformáticapt_BR
dc.publisher.initialsUFPBpt_BR
dc.subject.cnpqCNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAOpt_BR
Aparece nas coleções:TCC - Ciência da Computação - CI

Arquivos associados a este item:
Arquivo Descrição TamanhoFormato 
FCF19072017.pdf2,08 MBAdobe PDFVisualizar/Abrir
Mostrar registro simples do item Visualizar estatísticas


Este item está licenciada sob uma Licença Creative Commons Creative Commons