Complexidade de bem-cobertura sob parâmetros de distância para algumas classes de grafos

Detalhes bibliográficos
Ano de defesa: 2022
Autor(a) principal: Santos, Vinícius Gabriel lattes
Orientador(a): Santana, Márcia Rodrigues Cappelle lattes
Banca de defesa: Santana, Márcia Rodrigues Cappelle, Nascimento, Julliano Rosa, Sampaio, Rudini Menezes, Souza, Uéverton dos Santos
Tipo de documento: Dissertação
Tipo de acesso: Acesso aberto
Idioma: por
Instituição de defesa: Universidade Federal de Goiás
Programa de Pós-Graduação: Programa de Pós-graduação em Ciência da Computação (INF)
Departamento: Instituto de Informática - INF (RG)
País: Brasil
Palavras-chave em Português:
Palavras-chave em Inglês:
Área do conhecimento CNPq:
Link de acesso: http://repositorio.bc.ufg.br/tede/handle/tede/12051
Resumo: Let G = (V (G), E (G)) be a graph. A set I ⊆ V (G) is independent when any pairs of vertices belonging to I are not adjacent in G. An independent set is maximal if it is not properly contained in any other independent set of G. A graph G is well-covered if every maximal independent set of G is maximum. Determining whether a graph is well-covered is a coNP-complete problem. We present a kernelization algorithm for the problem of determining the WELL-COVERAGE for distance graphs for a class Q. Also results related to the intractability of WELL-COVERAGE parameterized for distance of free graphs of Cl with l ≥5. And finally, the inexistence of a polynomial kernel for WELL-COVERAGE parameterized by distance for cluster.