L(3,2,1)-Labeling on Graphs: Comparison between Greedy Heuristics and Genetic Algorithm - Queiroz, Jhon Kennedy C. de L.; Luiz, Atílio G. (Anais do Encontro Nacional de Inteligência Artificial e Computacional (ENIAC), 2025)
Diversos problemas de rotulação em grafos encontram aplicação na atribuição de canais de frequência a transmissores. Um deles é o Problema da Rotulação-L(3, 2, 1), no qual rótulos do conjunto {0, 1, . . . , k} são atribuídos aos vértices de um grafo de forma a satisfazer a restrição de que, para quaisquer dois vértices u, v ∈ V (G), deve-se ter que |f(u) − f(v)| ≥ 4 − dist(u, v), onde dist(u, v) é a distância entre u e v em G. Como esse problema é NP-completo, este trabalho propõe abordagens heurísticas e meta-heurísticas para obter soluções aproximadas. Foram implementados dois algoritmos gulosos e um algoritmo genético. Os resultados mostram que a abordagem gulosa é mais eficiente em tempo de execução, enquanto o algoritmo genético gera soluções de melhor qualidade.