文章基本信息

标题：Variable Neighborhood Search Approach for Solving Roman and Weak Roman Domination Problems on Graphs
本地全文：下载
作者：Ivanovićrija ; Urošević, Dragan
期刊名称：COMPUTING AND INFORMATICS
印刷版ISSN：1335-9150
出版年度：2019
卷号：38
期号：1
页码：57-84
出版社：COMPUTING AND INFORMATICS
摘要：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 justied 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.
其他摘要：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.
关键词：Roman domination in graphs; weak Roman domination in graphs; combinatorial optimization; metaheuristic; variable neighborhood search