O Jogo da Cobertura de Vértices em Grafos
Resumo
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.Referências
Brešar, B., Klavžar, S., and Rall, D. F. (2010). Domination game and an imagination strategy. SIAM J. Discrete Math., 24(3):979–991.
Brešar, B., Dorbec, P., Klavžar, S., Košmrlj, G., and Renault, G. (2016). Complexity of the game domination problem. Theoretical Computer Science, 648:1–7.
Brito, J. M., Marcilon, T., Martins, N. A., and Sampaio, R. M. (2026). The normal domination game in graphs. J. Comput. Syst. Sci., 157:103751.
Grundy, P. M. (1939). Mathematics and games. Eureka (The Archimedeans’ Journal), 2:6–8.
Sprague, R. (1936). Über mathematische Kampfspiele. Tôhoku Math J, 41:438–444.
Brešar, B., Dorbec, P., Klavžar, S., Košmrlj, G., and Renault, G. (2016). Complexity of the game domination problem. Theoretical Computer Science, 648:1–7.
Brito, J. M., Marcilon, T., Martins, N. A., and Sampaio, R. M. (2026). The normal domination game in graphs. J. Comput. Syst. Sci., 157:103751.
Grundy, P. M. (1939). Mathematics and games. Eureka (The Archimedeans’ Journal), 2:6–8.
Sprague, R. (1936). Über mathematische Kampfspiele. Tôhoku Math J, 41:438–444.
Publicado
19/07/2026
Como Citar
BASTOS, J.; BENEVIDES, F.; MARCILON, T.; MARTINS, N.; NISSE, N.; SAMPAIO, R..
O Jogo da Cobertura de Vértices em Grafos. In: ENCONTRO DE TEORIA DA COMPUTAÇÃO (ETC), 11. , 2026, Gramado/RS.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2026
.
p. 170-174.
ISSN 2595-6116.
DOI: https://doi.org/10.5753/etc.2026.22912.
