Meta-heuristic Algorithms for Double Roman Domination Problem
Himanshu Aggarwal, P. Venkata Subba Reddy · Applied Soft Computing · 2024
A variety of domination concepts have been defined to provide better routing and defense strategies under different constraints. A double Roman dominating function (DROMDF) on a simple, undirected graph G is a function g : V → { 0 , 1 , 2 , 3 } such that every vertex x ∈ V with g ( x ) = 0 is adjacent to at least two vertices y 1 , y 2 with g ( y 1 ) = g ( y 2 ) = 2 or a vertex z 1 with g ( z 1 ) = 3 . Also, a vertex p with g ( p ) = 1 is adjacent to at least one vertex q 1 with g ( q 1 ) ≥ 2 . γ d R ( G ) , the double Roman domination number of G , is the smallest possible weight of all possible DROMDFs of G . Determining double Roman domination number of a graph is known to be NP-hard. Hence in this paper, we propose a genetic algorithm based approach for solving double Roman domination problem in which three heuristic algorithms have been proposed and problem specific crossover operator and a feasibility function has been developed. Further, we propose an ant colony optimization algorithm to solve double Roman domination problem. This paper provides an in-depth illustration of two algorithms for solving double Roman domination problem. Effectiveness of the proposed meta-heuristic algorithms is tested on the random graphs generated using NetworkX Erdős-Rényi model, a popular model for graph generation and Harwell–Boeing dataset, a well-known dataset for graph related problems. Further, we compare the results of both the meta-heuristic algorithms and the experimental results show that the proposed meta-heuristic algorithms for solving double Roman domination problem give a near optimal solution in reasonable time. Experimental results also show that the proposed ant colony optimization algorithm for solving double Roman domination problem outperforms genetic algorithm based procedure.