Open Access

ARTICLE

Binary Archimedes Optimization Algorithm for Computing Dominant Metric Dimension Problem

by Basma Mohamed^1,*, 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

* Corresponding Author: Basma Mohamed. Email:

(This article belongs to the Special Issue: Soft Computing Methods for Intelligent Automation Systems)

Intelligent Automation & Soft Computing 2023, 38(1), 19-34. https://doi.org/10.32604/iasc.2023.031947

Received 01 May 2022; Accepted 14 October 2022; Issue published 26 January 2024

Abstract

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.

---

Keywords

---