Complexidade de bem-cobertura sob parâmetros de distância para algumas classes de grafos
I tiakina i:
| Kaituhi matua: | |
|---|---|
| Rā whakaputa: | 2022 |
| Hōputu: | Master thesis |
| Reo: | por |
| Puna: | Repositório Institucional da UFG |
| Download full: | http://repositorio.bc.ufg.br/tede/handle/tede/12051 |
Whakarāpopototanga: | 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. |