Issue |
RAIRO-Oper. Res.
Volume 58, Number 3, May-June 2024
|
|
---|---|---|
Page(s) | 2107 - 2121 | |
DOI | https://doi.org/10.1051/ro/2024074 | |
Published online | 24 May 2024 |
Metaheuristic algorithms for solving roman {2}-domination problem
Department of Computer Science and Engineering, National Institute of Technology Warangal, Hanamkonda 506004, Telangana, India
* Corresponding author: pvsr@nitw.ac.in
Received:
14
June
2023
Accepted:
24
March
2024
A Roman {2}-dominating function (Rom2DF) on a graph G(V, E) is a function g : V → {0, 1, 2} of G such that for every vertex x ∈ 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) = ∑x∈V g(x) is the weight of the Rom2DF. The minimum weight of a Rom2DF of G is called the Roman {2}-domination number denoted by γ{R2}(G). Since determining γ{R2}(G) of a graph G is NP-hard and no metaheuristic algorithms have been proposed for the same, two procedures based on genetic algorithm are proposed as a solution for the Roman {2}-domination problem. One of the proposed methods employs a random initial population, while the other uses a population generated using heuristics. Experiments have been carried out on graphs generated using Erdös–Rényi model, a popular model for graph generation and Harwell Boeing (HB) dataset. The experimental results demonstrate that both approaches provide a near optimal solution which is well within the known lower and upper bounds for the problem. The experimental results further show that the procedure based on random initial population has outperformed the heuristic based procedure.
Mathematics Subject Classification: 05C69 / 05C85 / 90C27 / 68W50
Key words: Domination number / Roman domination / Roman {2}-domination / NP-hard / genetic algorithm
© The authors. Published by EDP Sciences, ROADEF, SMAI 2024
This is an Open Access article distributed under the terms of the Creative Commons Attribution License (https://creativecommons.org/licenses/by/4.0), which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.