Detalhes bibliográficos
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: |
|
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. |