Skip navigation
DSpace logo

  1. Repositório Institucional da UFPB
  2. BDTD - UFPB
  3. UFPB - Campus I - João Pessoa
  4. Centro de Informática (CI) - Programa de Pós-Graduação em Informática
Use este identificador para citar ou linkar para este item: https://repositorio.ufpb.br/jspui/handle/123456789/18121
Registro completo de metadados
Campo DCValorIdioma
dc.creatorFragoso, Felipe Crispim-
dc.date.accessioned2020-10-14T13:18:19Z-
dc.date.available2020-10-13-
dc.date.available2020-10-14T13:18:19Z-
dc.date.issued2020-02-17-
dc.identifier.urihttps://repositorio.ufpb.br/jspui/handle/123456789/18121-
dc.description.abstractThe complete bipartite graph K1,3 is a tree known as claw. A graph is considered to be claw-free if it does not contain any induced subgraph isomorphic to the complete bipartite graph K1,3. Consider a graph G, the NP-Hard Graph Declawing Problem (GDP) consists of finding a minimum set S ⊆ V (G) such that G - S is claw-free. This research is a polyhedral study of the GDP polytope, expliciting its full dimensionality, proposing instances and four Branch-and-Cut algorithms with facet inequalities. Alongside that, two Branch-and-Price algorithms are proposed. The results for each algorithm are studied.pt_BR
dc.description.provenanceSubmitted by Cristhiane Guerra (cristhiane.guerra@academico.ufpb.br) on 2020-10-14T01:50:08Z No. of bitstreams: 2 license_rdf: 805 bytes, checksum: c4c98de35c20c53220c07884f4def27c (MD5) FelipeCrispimFragoso_Dissert.pdf: 17581936 bytes, checksum: 9eb796f9da545d5be213c2b298b70e99 (MD5)en
dc.description.provenanceApproved for entry into archive by Biblioteca Digital de Teses e Dissertações BDTD (bdtd@biblioteca.ufpb.br) on 2020-10-14T13:18:19Z (GMT) No. of bitstreams: 2 license_rdf: 805 bytes, checksum: c4c98de35c20c53220c07884f4def27c (MD5) FelipeCrispimFragoso_Dissert.pdf: 17581936 bytes, checksum: 9eb796f9da545d5be213c2b298b70e99 (MD5)en
dc.description.provenanceMade available in DSpace on 2020-10-14T13:18:19Z (GMT). No. of bitstreams: 2 license_rdf: 805 bytes, checksum: c4c98de35c20c53220c07884f4def27c (MD5) FelipeCrispimFragoso_Dissert.pdf: 17581936 bytes, checksum: 9eb796f9da545d5be213c2b298b70e99 (MD5) Previous issue date: 2020-02-17en
dc.description.sponsorshipCoordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPESpt_BR
dc.languageporpt_BR
dc.publisherUniversidade Federal da Paraíbapt_BR
dc.rightsAcesso abertopt_BR
dc.rights.urihttp://creativecommons.org/licenses/by-nd/3.0/br/*
dc.subjectProblema livre de garrapt_BR
dc.subjectCombinatória poliédricapt_BR
dc.subjectBranch-and-Cutpt_BR
dc.subjectBranch-and-Pricept_BR
dc.subjectGraph declawing problempt_BR
dc.subjectPolyhedral combinatoricspt_BR
dc.titleGraph declawing problem: polyhedra and exact solutionspt_BR
dc.typeDissertaçãopt_BR
dc.contributor.advisor1Sousa Filho, Gilberto Farias de-
dc.contributor.advisor1Latteshttp://lattes.cnpq.br/1129941438253617pt_BR
dc.contributor.advisor-co1Bulhões Júnior, Teobaldo Leite-
dc.contributor.advisor-co1Latteshttp://lattes.cnpq.br/3464164007134344pt_BR
dc.creator.Latteshttp://lattes.cnpq.br/3114692183689641pt_BR
dc.description.resumoO 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 de Eliminação de Garras (PEG) é NP-Completo e consiste em encontrar o conjunto de cardinalidade mínima S ⊆ V (G) tal que G - S é livre de garra. Este trabalho apresenta um estudo poliédrico do politopo associado ao PEG, explicitando sua dimensionalidade e revelando inequações definidoras de facetas. Além disso, instâncias aleatórias e intervalares foram construídas e utilizadas para execução de testes computacionais para quatro algoritmos Branch-and-Cut e dois algoritmos Branch-and-Price propostos.pt_BR
dc.publisher.countryBrasilpt_BR
dc.publisher.departmentInformáticapt_BR
dc.publisher.programPrograma de Pós-Graduação em Informáticapt_BR
dc.publisher.initialsUFPBpt_BR
dc.subject.cnpqCNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAOpt_BR
Aparece nas coleções:Centro de Informática (CI) - Programa de Pós-Graduação em Informática

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


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