Algoritmo Genético e Programa Linear Inteiro para o Problema da Dominação Romana Total - Cruz, Heric da Silva; Luiz, Atílio Gomes (Anais do Encontro de Teoria da Computação (ETC), 2025)
Dado um grafo G = (V,E), uma função f : V → {0, 1, 2} é uma função de dominação romana total (FDRT) se todo v ∈ V com f(v) = 0 possui um vizinho u ∈ V com f(u) = 2, e todo v ∈ V com f(v) > 0 possui um vizinho u ∈ V com f(u) > 0. O peso de f é ω(f) = ∑ v∈V f(v) e o número de dominação romana total de G é γ tR (G) = min{ω(f) : f é FDRT de G}. Neste trabalho, propomos um programa linear inteiro e um algoritmo genético para calcular γ tR (G), avaliando a eficácia deste último em instâncias diversas.