Binary Archimedes Optimization Algorithm for Computing Dominant Metric Dimension Problem  

作　　者：Basma Mohamed Linda Mohaisen Mohammed Amin 

机构地区：[1]Mathematics and Computer Science Department,Faculty of Science,Menoufia University,Shebin Elkom,32511,Egypt [2]Faculty of Computer and Information Technology,King Abdulaziz University,Jeddah,21589,Saudi Arabia

出　　处：《Intelligent Automation & Soft Computing》2023年第10期19-34,共16页智能自动化与软计算（英文）

摘　　要：In this paper,we consider the NP-hard problem of finding the minimum dominant resolving set of graphs.A vertex set B of a connected graph G resolves G if every vertex of G is uniquely identified by its vector of distances to the vertices in B.A resolving set is dominating if every vertex of G that does not belong to B is a neighbor to some vertices in B.The dominant metric dimension of G is the cardinality number of the minimum dominant resolving set.The dominant metric dimension is computed by a binary version of the Archimedes optimization algorithm(BAOA).The objects of BAOA are binary encoded and used to represent which one of the vertices of the graph belongs to the dominant resolving set.The feasibility is enforced by repairing objects such that an additional vertex generated from vertices of G is added to B and this repairing process is iterated until B becomes the dominant resolving set.This is the first attempt to determine the dominant metric dimension problem heuristically.The proposed BAOA is compared to binary whale optimization(BWOA)and binary particle optimization(BPSO)algorithms.Computational results confirm the superiority of the BAOA for computing the dominant metric dimension.

关 键 词：Dominant metric dimension archimedes optimization algorithm binary optimization alternate snake graphs 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]