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

• Ano de defesa: 2022
• Autor(a) principal: Santos, Vinícius Gabriel
• Orientador(a): Santana, Márcia Rodrigues Cappelle
• 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: Teoria dos Grafos; Complexidade parametrizada e bem-cobertura
• Palavras-chave em Inglês: Graph theory; Parameterized complexity and well-covered graphs
• Área do conhecimento CNPq: CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO::TEORIA DA COMPUTACAO
• Link de acesso: http://repositorio.bc.ufg.br/tede/handle/tede/12051

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.