Algoritmos FPT para reconhecer grafos bem cobertos - Araújo, Rafael T.; Klein, Sulamita; Sampaio, Rudini (Anais do Encontro de Teoria da Computação (ETC); 2018: Anais do III Encontro de Teoria da ComputaçãoDO - 10.5753/etc.2018.3140, 2018)
Dado um grafo G, sejam vc(G) e vc + (G) os tamanhos de uma cobertura mínima de vértices e de uma máxima cobertura minimal de vértices, respectivamente. Dizemos que G é bem coberto se vc(G) = vc + (G) (ou seja, todas as coberturas minimais são mínimas). É coNP-completo decidir se um grafo é bem coberto. Nesse artigo, obtemos algoritmos FPT de tempos O ∗ (2 vc ) e O ∗ (1.4656 vc+ ) para decidir se um grafo é bem coberto, parametrizados por vc(G) e vc + (G), respectivamente, melhorando resultados de Boria et al. em 2015. Também obtemos algoritmo FPT parametrizado por α(G) = n - vc(G) em grafos d-degenerados, que inclui grafos com genus limitado (como grafos planares) e grafos com grau máximo limitado. Finalmente usamos a decomposição primeval para obter algoritmo linear para grafos P 4 -laden estendidos e grafos (q, q 4), que é FPT parametrizado por q, melhorando resultados de Klein et al. em 2013.