Metaheuristic algorithms for solving Roman \(\{2\}\)-domination problem (Q6550850)

A Roman \(\{2\}\)-dominating function (Rom2DF) on a graph \(G=(V,E)\) is a function \(g:V\rightarrow \{0, 1, 2\}\) of \(G\) such that for every vertex \(x\in V\) with \(g(x)=0\), either there exists a neighbor \(y\) of \(x\) with \(g(y)=2\) or at least two neighbors, \(u\), \(v\) with \(g(u)=g(v)=1\). The value \(w(g)=\sum_{x\in V}g(x)\) is the weight of the Rom2DF. The minimum weight of a Rom2DF of \(G\) is called the Roman \(\{2\}\)-domination number which is denoted by \(\gamma_{\{R2\}}(G)\). In this paper, the authors propose two procedures based on a genetic algorithm for determining \(\gamma_{\{R2\}}(G)\).\N\NA brief introduction to genetic algorithms is given in Section 2. In Sections 3 and 4, two procedures for determining \(\gamma_{\{R2\}}(G)\) are presented. It is observed that procedure 1, which uses a random initial population has outperformed procedure 2 which is a heuristic-based approach in many cases.