Graph declawing problem: polyhedra and exact solutions

Detalhes bibliográficos
Ano de defesa:	2020
Autor(a) principal:	Fragoso, Felipe Crispim
Orientador(a):	Não Informado pela instituição
Banca de defesa:	Não Informado pela instituição
Tipo de documento:	Dissertação
Tipo de acesso:	Acesso aberto
Idioma:	por
Instituição de defesa:	Universidade Federal da Paraíba Brasil Informática Programa de Pós-Graduação em Informática UFPB
Programa de Pós-Graduação:	Não Informado pela instituição
Departamento:	Não Informado pela instituição
País:	Não Informado pela instituição
Palavras-chave em Português:	Problema livre de garra Combinatória poliédrica Branch-and-Cut Branch-and-Price Graph declawing problem Polyhedral combinatorics CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO
Link de acesso:	https://repositorio.ufpb.br/jspui/handle/123456789/18121
Resumo:	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.

Registros relacionados