Metaheuristic algorithms for solving Roman \(\{2\}\)-domination problem
type: Item
instance of: scholarly article
title: Metaheuristic algorithms for solving Roman \(\{2\}\)-domination problem
zbMATH Open document ID: 1540.0514
author: M. Alfred Raju
author: P. Venkata Subba Reddy
published in: RAIRO. Operations Research
publication date: 2024-06-05T00:00:00Z
review text: 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.
reviewed by: Saeid Alikhani
Mathematics Subject Classification ID: 05C69
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 90C27
Mathematics Subject Classification ID: 68W50
zbMATH DE Number: 7860531
zbMATH Keywords: domination number
zbMATH Keywords: Roman domination
zbMATH Keywords: Roman \(\{2\}\)-domination
zbMATH Keywords: NP-hard
zbMATH Keywords: genetic algorithm
MaRDI profile type: MaRDI publication profile
cites work: Roman domination in graphs.
cites work: Roman \(\{2 \}\)-domination
cites work: Q4368728
cites work: Italian domination on Mycielskian and Sierpinski graphs
cites work: Varieties of Roman domination. II
cites work: Complexity of Roman \(\{ 2 \} \)-domination and the double Roman domination in graphs
cites work: On a feasible-infeasible two-population (FI-2Pop) genetic algorithm for constrained optimization: Distance tracing and no free lunch
cites work: Italian domination in the Cartesian product of paths
DOI: 10.1051/RO/2024074
Recommended article: Roman \(\{2\}\)-domination problem in graphs
Recommended article: Complexity of Roman \(\{ 2 \} \)-domination and the double Roman domination in graphs
Recommended article: Roman \(\{2 \}\)-domination
Recommended article: On the computational complexity of Roman\(\{2\}\)-domination in grid graphs
Recommended article: Roman \([1,2]\)-domination of graphs
copyright license: Creative Commons Attribution 4.0 International
description: scientific article; zbMATH DE number 7860531