O Jogo da Cobertura de Vértices em Grafos - Bastos, J.; Benevides, F.; Marcilon, T.; Martins, N.; Nisse, N.; Sampaio, R. (Anais do Encontro de Teoria da Computação (ETC), 2026)
Nesse artigo, nós introduzimos o Jogo da Cobertura de Vértices em grafos. Com relação à variante principal (de otimização), nós determinamos o vencedor em florestas de estrelas e grafos multipartido completos, além de obter um algoritmo polinomial 2-aproximativo e um algorimo FPT parametrizado pelo número de vértices selecionados. Com relação à variante normal, determinamos o vencedor de qualquer grafo multipartido completo.