2022-05-102022-05-102022-04-18SANTOS, V. G. Complexidade de bem-cobertura sob parâmetros de distância para algumas classes de grafos. 2022. 75 f. Dissertação (Mestrado em Ciência da Computação) - Universidade Federal de Goiás, Goiânia, 2022.http://repositorio.bc.ufg.br/tede/handle/tede/12051Let 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.Attribution-NonCommercial-NoDerivatives 4.0 InternationalTeoria dos GrafosComplexidade parametrizada e bem-coberturaGraph theoryParameterized complexity and well-covered graphsCIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO::TEORIA DA COMPUTACAODissertação