Algoritmo Genético e Programa Linear Inteiro para o Problema da Dominação Romana Total
Resumo
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.
Referências
Abdollahzadeh Ahangar, H., Henning, M., Samodivkin, V., and G. Yero, I. (2016). Total roman domination in graphs. Applicable Analysis and Discrete Mathematics, 10:17–17.
Billore, A. and Reddy, P. V. S. (2023). Genetic algorithm based approach for solving roman 3-domination problem. In 2023 International Conference on Computer, Electronics & Electrical Engineering & their Applications (IC2E3), pages 1–6.
Cai, Q., Fan, N., Shi, Y., and and, S. Y. (2022). Integer linear programming formulations for double roman domination problem. Optimization Methods and Software, 37(1):1–22.
Cockayne, E. J., Dreyer, P. A., Hedetniemi, S. M., and Hedetniemi, S. T. (2004). Roman domination in graphs. Discrete Mathematics, 278(1):11–22.
Goldberg, D. E. (1989). Genetic Algorithms in Search, Optimization and Machine Learning. Addison-Wesley Longman Publishing Co., Inc., USA, 1st edition.
Goldberg, D. E. and Deb, K. (1991). A comparative analysis of selection schemes used in genetic algorithms. volume 1 of Foundations of Genetic Algorithms, pages 69–93. Elsevier.
Holland, J. H. (1992). Adaptation in Natural and Artificial Systems: An Introductory Analysis with Applications to Biology, Control and Artificial Intelligence. MIT Press, Cambridge, MA, USA.
Katoch, S., Chauhan, S. S., and Kumar, V. (2021). A review on genetic algorithm: past, present, and future. Multimedia Tools and Applications, 80:8091–8126.
Khandelwal, A., Srivastava, K., and Saran, G. (2021). On roman domination of graphs using a genetic algorithm. In Singh, V., Asari, V. K., Kumar, S., and Patel, R. B., editors, Computational Methods and Data Engineering, pages 133–147, Singapore. Springer Singapore.
Kora, P. and Yadlapalli, P. (2017). Crossover operators in genetic algorithms: A review. International Journal of Computer Applications, 162:34–36.
Liu, C.-H. and Chang, G. J. (2013). Roman domination on strongly chordal graphs. Journal of Combinatorial Optimization, 26(3):608–619.
López-Ibáñez, M., Dubois-Lacoste, J., Pérez Cáceres, L., Birattari, M., and Stützle, T. (2016). The irace package: Iterated racing for automatic algorithm configuration. Operations Research Perspectives, 3:43–58.
National Institute of Standards and Technology. Matrix Market: A Visual Repository of Test Data for Sparse Matrix Algorithms. Disponível em: [link]. Data de acesso: Março de 2025.
Poureidi, A. and Fathali, J. (2023). Algorithmic results in roman dominating functions on graphs. Information Processing Letters, 182:106363.
Rossi, R. A. and Ahmed, N. K. (2015). The network data repository with interactive graph analytics and visualization. In AAAI. Disponível em: [link]. Data de acesso: Março de 2025.
Billore, A. and Reddy, P. V. S. (2023). Genetic algorithm based approach for solving roman 3-domination problem. In 2023 International Conference on Computer, Electronics & Electrical Engineering & their Applications (IC2E3), pages 1–6.
Cai, Q., Fan, N., Shi, Y., and and, S. Y. (2022). Integer linear programming formulations for double roman domination problem. Optimization Methods and Software, 37(1):1–22.
Cockayne, E. J., Dreyer, P. A., Hedetniemi, S. M., and Hedetniemi, S. T. (2004). Roman domination in graphs. Discrete Mathematics, 278(1):11–22.
Goldberg, D. E. (1989). Genetic Algorithms in Search, Optimization and Machine Learning. Addison-Wesley Longman Publishing Co., Inc., USA, 1st edition.
Goldberg, D. E. and Deb, K. (1991). A comparative analysis of selection schemes used in genetic algorithms. volume 1 of Foundations of Genetic Algorithms, pages 69–93. Elsevier.
Holland, J. H. (1992). Adaptation in Natural and Artificial Systems: An Introductory Analysis with Applications to Biology, Control and Artificial Intelligence. MIT Press, Cambridge, MA, USA.
Katoch, S., Chauhan, S. S., and Kumar, V. (2021). A review on genetic algorithm: past, present, and future. Multimedia Tools and Applications, 80:8091–8126.
Khandelwal, A., Srivastava, K., and Saran, G. (2021). On roman domination of graphs using a genetic algorithm. In Singh, V., Asari, V. K., Kumar, S., and Patel, R. B., editors, Computational Methods and Data Engineering, pages 133–147, Singapore. Springer Singapore.
Kora, P. and Yadlapalli, P. (2017). Crossover operators in genetic algorithms: A review. International Journal of Computer Applications, 162:34–36.
Liu, C.-H. and Chang, G. J. (2013). Roman domination on strongly chordal graphs. Journal of Combinatorial Optimization, 26(3):608–619.
López-Ibáñez, M., Dubois-Lacoste, J., Pérez Cáceres, L., Birattari, M., and Stützle, T. (2016). The irace package: Iterated racing for automatic algorithm configuration. Operations Research Perspectives, 3:43–58.
National Institute of Standards and Technology. Matrix Market: A Visual Repository of Test Data for Sparse Matrix Algorithms. Disponível em: [link]. Data de acesso: Março de 2025.
Poureidi, A. and Fathali, J. (2023). Algorithmic results in roman dominating functions on graphs. Information Processing Letters, 182:106363.
Rossi, R. A. and Ahmed, N. K. (2015). The network data repository with interactive graph analytics and visualization. In AAAI. Disponível em: [link]. Data de acesso: Março de 2025.
Publicado
20/07/2025
Como Citar
CRUZ, Heric da Silva; LUIZ, Atílio Gomes.
Algoritmo Genético e Programa Linear Inteiro para o Problema da Dominação Romana Total. In: ENCONTRO DE TEORIA DA COMPUTAÇÃO (ETC), 10. , 2025, Maceió/AL.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2025
.
p. 26-30.
ISSN 2595-6116.
DOI: https://doi.org/10.5753/etc.2025.8041.
