Roman domination is a well researched topic in graph theory. Recently two new variants of Roman domination, namely triple Roman domination and quadruple Roman domination problems have been introduced, to provide better defense strategies. However, triple Roman domination and quadruple Roman domination problems are NP-hard. In this paper, we have provided genetic algorithm for solving triple and quadruple Roman domination problems. Programming (ILP) formulations for triple Roman domination and quadruple Roman domination problems have been proposed. The proposed models are implemented using IBM CPLEX 22.1 optimization solvers and obtained results for random graphs generated using NetworkX Erdos-Renyi model.
翻译：罗马占领是图论中的一个研究方向。近来，为了提供更好的防御策略，人们引入了两个新的罗马占领变体，即三元罗马占领和四元罗马占领问题。然而，三元罗马占领和四元罗马占领问题都是NP难问题。本文提出了遗传算法解决三元和四元罗马占领问题。我们还为这两个问题提出了整数线性规划模型。使用IBM CPLEX 22.1优化求解器实现了所提出的模型，并在使用NetworkX Erdos-Renyi模型生成的随机图上获得了结果。
相关内容
微信扫码咨询专知VIP会员