Authors: Ivanović, Marija
Urošević, Dragan 
Title: Variable neighborhood search approach for solving Roman and weak Roman domination problems on graphs
Journal: Computing and Informatics
Volume: 38
Issue: 1
First page: 57
Last page: 84
Issue Date: 1-Jan-2019
Rank: M23
ISSN: 1335-9150
DOI: 10.31577/cai_2019_1_57
In this paper Roman and weak Roman domination problems on graphs are considered. Given that both problems are NP hard, a new heuristic approach, based on a Variable Neighborhood Search (VNS), is presented. The presented algorithm is tested on instances known from the literature, with up to 600 vertices. The VNS approach is justified since it was able to achieve an optimal solution value on the majority of instances where the optimal solution value is known. Also, for the majority of instances where optimization solvers found a solution value but were unable to prove it to be optimal, the VNS algorithm achieves an even better solution value.
Keywords: Combinatorial optimization | Metaheuristic | Roman domination in graphs | Variable neighborhood search | Weak Roman domination in graphs
Publisher: Slovak Academy of Sciences
Project: Optimization of Distributive and Reverse Flows in Logistic Systems 
Mathematical Modelas and Optimization Methods on Large-Scale Systems 

Show full item record


checked on Jun 12, 2024

Page view(s)

checked on May 9, 2024

Google ScholarTM




Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.