Repositório Institucional da UFPB
Use este identificador para citar ou linkar para este item:
https://repositorio.ufpb.br/jspui/handle/123456789/18121| Tipo: | Dissertação |
| Título: | Graph declawing problem: polyhedra and exact solutions |
| Autor(es): | Fragoso, Felipe Crispim |
| Primeiro Orientador: | Sousa Filho, Gilberto Farias de |
| Primeiro Coorientador: | Bulhões Júnior, Teobaldo Leite |
| 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 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. |
| Abstract: | The 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. |
| Palavras-chave: | Problema livre de garra Combinatória poliédrica Branch-and-Cut Branch-and-Price Graph declawing problem Polyhedral combinatorics |
| CNPq: | CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO |
| Idioma: | por |
| País: | Brasil |
| Editor: | Universidade Federal da Paraíba |
| Sigla da Instituição: | UFPB |
| Departamento: | Informática |
| Programa: | Programa de Pós-Graduação em Informática |
| Tipo de Acesso: | Acesso aberto |
| URI: | http://creativecommons.org/licenses/by-nd/3.0/br/ |
| URI: | https://repositorio.ufpb.br/jspui/handle/123456789/18121 |
| Data do documento: | 17-Fev-2020 |
| 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 | Tamanho | Formato | |
|---|---|---|---|---|
| FelipeCrispimFragoso_Dissert.pdf | 17,17 MB | Adobe PDF | Visualizar/Abrir |
Este item está licenciada sob uma
Licença Creative Commons
