L(3,2,1)-Labeling on Graphs: Comparison between Greedy Heuristics and Genetic Algorithm
Resumo
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.
Referências
Calamoneri, T. (2006). The l(h, k)-labelling problem: A survey and annotated bibliography. The Computer Journal, 49(5):585–608.
CELAR (2025). Celar radio link frequency assignment instances. [link]. Acesso em 2025.
Chia, M. L., Kuo, D., Yang, H. L. C. H., and Yeh, R. K. (2011). L(3,2,1) labeling of graphs. Taiwanese Journal of Mathematics, 15:2439–2457.
Clipperton, J., Gehrtz, J., Szaniszlo, Z., and Torkornoo, D. (2005). L(3,2,1)-labeling of simple graphs. In Proceedings of the 36th Southeastern International Conference on Combinatorics, Graph Theory and Computing, pages 1–14.
Cormen, T. H., Leiserson, C. E., Rivest, R. L., and Stein, C. (2009). Introduction to Algorithms. MIT press, 3 edition.
Duff, I. S., Grimes, R. G., and Lewis, J. G. (2025). Harwell-boeing sparse matrix collection. [link]. Acesso em 2025.
Florencio, D. G. and Luiz, A. G. (2021). Limites superiores para a rotulação-L(3,2,1) de grafos com grau máximo três. In Anais do LIII Simpósio Brasileiro de Pesquisa Operacional (SBPO), pages 11–15, João Pessoa, Brasil. Galoá.
Gen, M. and Cheng, R. (1997). Genetic Algorithms and Engineering Design. John Wiley & Sons, New York.
Goldberg, D. E. (1989). Genetic Algorithms in Search, Optimization and Machine Learning. Addison-Wesley, Boston.
Griggs, J. R. and Yeh, R. K. (1992). Labelling graphs with a condition at distance 2. SIAM Journal on Discrete Mathematics, 5(4):586–595.
Hagberg, A. A., Schult, D. A., and Swart, P. J. (2008). Networkx: Python software for the analysis of networks. Disponível em: [link].
Hale, W. K. (1980). Frequency assignment: Theory and applications. Proceedings of the IEEE, 68(12):1497–1514.
Han, K. and Kim, C. (2008). Solving l(2,1)-labeling problem of graphs using genetic algorithms. The KIPS Transactions:PartB, 15B(2):131–136.
Hart, E., Ross, P., and Nelson, J. (2005). A survey of hybrid metaheuristics. Studies in Computational Intelligence, 1:1–26.
Holland, J. H. (1975). Adaptation in Natural and Artificial Systems. University of Michigan Press, Ann Arbor, MI.
Jansky, D. (1977). Spectrum Management Techniques. Multi-volume EMC encyclopedia series. Don White Consultants.
Johnson, D. S. and Trick, M. A. (1996). Cliques, coloring, and satisfiability: Second dimacs implementation challenge. In DIMACS Series in Discrete Mathematics and Theoretical Computer Science, volume 26. American Mathematical Society.
Mitchell, M. (1998). An Introduction to Genetic Algorithms. MIT Press, Cambridge, MA.
Mumford, C. L. (2006). New order-based crossovers for the graph coloring problem. In Runarsson, T. P., Beyer, H.-G., Burke, E., Merelo-Guervós, J. J., Whitley, L. D., and Yao, X., editors, Parallel Problem Solving from Nature - PPSN IX, pages 880–889, Berlin, Heidelberg. Springer Berlin Heidelberg.
Murphey, R. A., Pardalos, P. M., and Resende, M. G. C. (1999). Frequency Assignment Problems, pages 295–377. Springer US, Boston, MA.
Panda, B. S. and Goel, P. (2010). Heuristic algorithms for the l(2,1)-labeling problem. Lecture Notes in Computer Science,Swarm, Evolutionary, and Memetic Computing, Not available:214–221.
Shao, J. and Liu, X. (2004). Labeling graphs with maximum degree three and four. Discrete Mathematics, 275(1-3):339–349.
Shao, Z. and Vesel, A. (2013). Integer linear programming model and satisfiability test reduction for distance constrained labellings of graphs: the case of l(3,2,1)labelling for products of paths and cycles. IET Communications, 7(8):715–720.
CELAR (2025). Celar radio link frequency assignment instances. [link]. Acesso em 2025.
Chia, M. L., Kuo, D., Yang, H. L. C. H., and Yeh, R. K. (2011). L(3,2,1) labeling of graphs. Taiwanese Journal of Mathematics, 15:2439–2457.
Clipperton, J., Gehrtz, J., Szaniszlo, Z., and Torkornoo, D. (2005). L(3,2,1)-labeling of simple graphs. In Proceedings of the 36th Southeastern International Conference on Combinatorics, Graph Theory and Computing, pages 1–14.
Cormen, T. H., Leiserson, C. E., Rivest, R. L., and Stein, C. (2009). Introduction to Algorithms. MIT press, 3 edition.
Duff, I. S., Grimes, R. G., and Lewis, J. G. (2025). Harwell-boeing sparse matrix collection. [link]. Acesso em 2025.
Florencio, D. G. and Luiz, A. G. (2021). Limites superiores para a rotulação-L(3,2,1) de grafos com grau máximo três. In Anais do LIII Simpósio Brasileiro de Pesquisa Operacional (SBPO), pages 11–15, João Pessoa, Brasil. Galoá.
Gen, M. and Cheng, R. (1997). Genetic Algorithms and Engineering Design. John Wiley & Sons, New York.
Goldberg, D. E. (1989). Genetic Algorithms in Search, Optimization and Machine Learning. Addison-Wesley, Boston.
Griggs, J. R. and Yeh, R. K. (1992). Labelling graphs with a condition at distance 2. SIAM Journal on Discrete Mathematics, 5(4):586–595.
Hagberg, A. A., Schult, D. A., and Swart, P. J. (2008). Networkx: Python software for the analysis of networks. Disponível em: [link].
Hale, W. K. (1980). Frequency assignment: Theory and applications. Proceedings of the IEEE, 68(12):1497–1514.
Han, K. and Kim, C. (2008). Solving l(2,1)-labeling problem of graphs using genetic algorithms. The KIPS Transactions:PartB, 15B(2):131–136.
Hart, E., Ross, P., and Nelson, J. (2005). A survey of hybrid metaheuristics. Studies in Computational Intelligence, 1:1–26.
Holland, J. H. (1975). Adaptation in Natural and Artificial Systems. University of Michigan Press, Ann Arbor, MI.
Jansky, D. (1977). Spectrum Management Techniques. Multi-volume EMC encyclopedia series. Don White Consultants.
Johnson, D. S. and Trick, M. A. (1996). Cliques, coloring, and satisfiability: Second dimacs implementation challenge. In DIMACS Series in Discrete Mathematics and Theoretical Computer Science, volume 26. American Mathematical Society.
Mitchell, M. (1998). An Introduction to Genetic Algorithms. MIT Press, Cambridge, MA.
Mumford, C. L. (2006). New order-based crossovers for the graph coloring problem. In Runarsson, T. P., Beyer, H.-G., Burke, E., Merelo-Guervós, J. J., Whitley, L. D., and Yao, X., editors, Parallel Problem Solving from Nature - PPSN IX, pages 880–889, Berlin, Heidelberg. Springer Berlin Heidelberg.
Murphey, R. A., Pardalos, P. M., and Resende, M. G. C. (1999). Frequency Assignment Problems, pages 295–377. Springer US, Boston, MA.
Panda, B. S. and Goel, P. (2010). Heuristic algorithms for the l(2,1)-labeling problem. Lecture Notes in Computer Science,Swarm, Evolutionary, and Memetic Computing, Not available:214–221.
Shao, J. and Liu, X. (2004). Labeling graphs with maximum degree three and four. Discrete Mathematics, 275(1-3):339–349.
Shao, Z. and Vesel, A. (2013). Integer linear programming model and satisfiability test reduction for distance constrained labellings of graphs: the case of l(3,2,1)labelling for products of paths and cycles. IET Communications, 7(8):715–720.
Publicado
29/09/2025
Como Citar
QUEIROZ, Jhon Kennedy C. de L.; LUIZ, Atílio G..
L(3,2,1)-Labeling on Graphs: Comparison between Greedy Heuristics and Genetic Algorithm. In: ENCONTRO NACIONAL DE INTELIGÊNCIA ARTIFICIAL E COMPUTACIONAL (ENIAC), 22. , 2025, Fortaleza/CE.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2025
.
p. 1257-1268.
ISSN 2763-9061.
DOI: https://doi.org/10.5753/eniac.2025.14495.
