Determining the Mixed Metric Dimension of a Graph with the Binary Gray Wolf Algorithm
DOI:
https://doi.org/10.22452/mjs.vol45sp2.5Keywords:
Binary gray wolf optimizer algorithm, edge metric dimension (EMD), mixed metric dimension (MMD)Abstract
Many computational techniques for extracting insights from data depend on embedding data within a Euclidean space. However, symbolic datasets, particularly biological sequence datasets resulting from high-throughput sequencing processes, often pose challenges for conventional embedding methods, as they tend to yield either excessively high-dimensional or overly simplified representations, thereby limiting their analytical applicability. To address these constraints, the concept of metric dimension (MD) in graph theory provides a rigorous and practical framework for representing points in the Euclidean plane based on their relative distances. In this study, we explore a hybrid concept that combines two distance parameters: MD and edge metric dimension (EMD). The mixed metric dimension (MMD) uniquely characterizes a graph’s elements (edges and vertices) based on their distance vectors to a designated set of vertices. We developed a computational intelligence approach to determine the mixed metric dimension of graphs: the Binary Gray Wolf Optimizer (BGWO) algorithm. We integrate a distance-based matrix representation with population-based optimization methods. To improve solution performance, several modifications have been incorporated, including the validation of row uniqueness, the implementation of dynamic stagnation handling techniques, and the adoption of an elitism strategy. Our findings indicate that the BGWO achieves efficient completion times and delivers competitive performance for this problem.
References
Abbas, Waseem et al. 2024. “Investigating Metric Dimension and Edge Metric Dimension of Hexagonal Boron Nitride and Carbon Nanotubes.” European Journal of Pure and Applied Mathematics 17(3): 2055–72.
Beerliova, Zuzana et al. 2006. “Network Discovery and Verification.” IEEE Journal on Selected Areas in Communications 24(12): 2168–81.
Chartrand, Gary, Linda Eroh, Mark A. Johnson, and Ortrud R. Oellermann. 2000. “Resolvability in Graphs and the Metric Dimension of a Graph.” Discrete Applied Mathematics 105(1–3): 99–113.
Chelladurai, Xavier. 2020. “Algorithms for the Metric Dimension of a Simple Graph.” Data Science and Security, Lectures Notes in Network and Systems (132): 91–105.
Chen, Xujin, Xiaodong Hu, and Changjun Wang. 2016. “Approximation for the Minimum Cost Doubly Resolving Set Problem.” Theoretical Computer Science 609: 526–43. http://dx.doi.org/10.1016/j.tcs.2015.03.048.
Danas, Milica Milivojević. 2021. “The Mixed Metric Dimension of Flower Snarks and Wheels.” Open Mathematics 19(1): 629–40.
Darmaji, and N. Azahra. 2022. “The Mixed Metric Dimension of Wheel-like Graphs.” Journal of Physics: Conference Series 2157(1).
Diaz, Josep, Olli Pottonen, Maria Serna, and Erik Jan van Leeuwen. 2017. “Complexity of Metric Dimension on Planar Graphs.” Journal of Computer and System Sciences 83(1): 132–58. http://dx.doi.org/10.1016/j.jcss.2016.06.006.
Emary, E., Hossam M. Zawbaa, and Aboul Ella Hassanien. 2016. “Binary Grey Wolf Optimization Approaches for Feature Selection.” Neurocomputing 172: 371–81. http://dx.doi.org/10.1016/j.neucom.2015.06.083.
Harrary, F, and R.A Melter. 1976. “On the Metric Dimension of a Graph.” Ars Combin 2: 191–95.
Hauptmann, Mathias, Richard Schmied, and Claus Viehmann. 2012. “Approximation Complexity of Metric Dimension Problem.” Journal of Discrete Algorithms 14: 214–22. http://dx.doi.org/10.1016/j.jda.2011.12.010.
Hendy, Hendy, Mohammad Isa, Imam Mukhlash, and Samsul Setumin. 2023. “A Bibliometric Analysis of Metaheuristic Research and Its Applications.” Register: Jurnal Ilmiah Teknologi Sistem Informasi 9(January): 1–17. http://www.journal.unipdu.ac.id/index.php/register/article/view/2675.
Hertz, Alain. 2020. “An IP-Based Swapping Algorithm for the Metric Dimension and Minimal Doubly Resolving Set Problems in Hypercubes.” Optimization Letters 14(2): 355–67.
Hoffmann, Stefan, Alina Elterman, and Egon Wanke. 2016. “A Linear Time Algorithm for Metric Dimension of Cactus Block Graphs.” Theoretical Computer Science 630: 43–62. http://dx.doi.org/10.1016/j.tcs.2016.03.024.
Imran, Muhammad, Ali Ahmad, Muhammad Azeem, and Kashif Elahi. 2022. “Metric-Based Resolvability of Quartz Structure.” Computers, Materials and Continua 71(1): 2053–71.
Kelenc, Aleksander, Dorota Kuziak, Andrej Taranenko, and Ismael G. Yero. 2017. “Mixed Metric Dimension of Graphs.” Applied Mathematics and Computation 314: 429–38. http://dx.doi.org/10.1016/j.amc.2017.07.027.
Kelenc, Aleksander, Niko Tratnik, and Ismael G. Yero. 2018. “Uniquely Identifying the Edges of a Graph: The Edge Metric Dimension.” Discrete Applied Mathematics 251(January 2016): 204–20.
Khuller, Samir, Balaji Raghavachari, and Azriel Rosenfeld. 1996. “Landmarks in Graphs.” Discrete Applied Mathematics 70(3): 217–29.
Knor, Martin et al. 2021. “Graphs with the Edge Metric Dimension Smaller than the Metric Dimension.” Applied Mathematics and Computation 401.
Koam, Ali N.A., Ali Ahmad, Sadia Husain, and Muhammad Azeem. 2023. “Mixed Metric Dimension of Hollow Coronoid Structure.” Ain Shams Engineering Journal 14(7): 102000. https://doi.org/10.1016/j.asej.2022.102000.
Kratica, Jozef, Vera Kovačević-Vujčić, and Mirjana Čangalović. 2009. “Computing the Metric Dimension of Graphs by Genetic Algorithms.” Computational Optimization and Applications 44(2): 343–61.
Kratica, Jozef, Vera Kovačević-Vujčić, Mirjana Čangalović, and Milica Stojanović. 2012. “Minimal Doubly Resolving Sets and the Strong Metric Dimension of Some Convex Polytopes.” Applied Mathematics and Computation 218(19): 9790–9801.
Melter, Robert A., and Ioan Tomescu. 1984. “Metric Bases in Digital Geometry.” Computer Vision, Graphics and Image Processing 25(1): 113–21.
Mirjalili, Seyedali, Seyed Mohammad Mirjalili, and Andrew Lewis. 2014. “Grey Wolf Optimizer.” Advances in Engineering Software 69: 46–61. http://dx.doi.org/10.1016/j.advengsoft.2013.12.007.
Mladenović, Nenad, Jozef Kratica, Vera Kovačević-Vujčić, and Mirjana Čangalović. 2012. “Variable Neighborhood Search for Metric Dimension and Minimal Doubly Resolving Set Problems.” European Journal of Operational Research 220(2): 328–37.
Mohame, Basma, Mohammed Ami, and Linda Mohaise. 2023. “Binary Archimedes Optimization Algorithm for Computing Dominant Metric Dimension Problem.” Intelligent Automation and Soft Computing 38(1): 19–34.
Muhammad, F., and L. Susilowati. 2020. “Algorithm and Computer Program to Determine Metric Dimension of Graph.” Journal of Physics: Conference Series 1494(1): 0–5.
Murdiansyah, D.T, and Adiwijaya. 2017. “Computing the Metric Dimension of Hypercube Graphs by Particle Swarm Optimization Algorithm.” Recent Advances on Soft Computing and Data Mining, Advances in Intelligent Systems and Computing 549.
Peterin, Iztok, and Ismael G. Yero. 2020. “Edge Metric Dimension of Some Graph Operations.” Bulletin of the Malaysian Mathematical Sciences Society 43(3): 2465–77. https://doi.org/10.1007/s40840-019-00816-7.
Seb, Andris, and Eric Tannier. 2016. “On Metric Generators of Graphs Author ( s ): András Sebő and Eric Tannier Published by : INFORMS Stable URL : Http://Www.Jstor.Org/Stable/30035689 On Metric Generators of Graphs.” 29(2): 383–93.
Sedlar, Jelena, and Riste Škrekovski. 2021a. “Extremal Mixed Metric Dimension with Respect to the Cyclomatic Number.” Applied Mathematics and Computation 404: 126238. https://doi.org/10.1016/j.amc.2021.126238.
Sedlar, Jelena, and Riste Škrekovski.. 2021b. “Mixed Metric Dimension of Graphs with Edge Disjoint Cycles.” Discrete Applied Mathematics 300: 1–8. https://doi.org/10.1016/j.dam.2021.05.004.
Slater, P.J. 1975. “Leaves of Trees.” Congr. Numer 14: 549–59.
Tillquist, Richard C., and Manuel E. Lladser. 2019. “Low-Dimensional Representation of Genomic Sequences.” Journal of Mathematical Biology. https://doi.org/10.1007/s00285-019-01348-1.
Vietz, Duygu, Stefan Hoffmann, and Egon Wanke. 2019. 11355 LNCS Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) Computing the Metric Dimension by Decomposing Graphs into Extended Biconnected Components: (Extended Abstract). Springer International Publishing. http://dx.doi.org/10.1007/978-3-030-10564-8_14.
Zhang, Yuezhong, and Suogang Gao. 2020. “On the Edge Metric Dimension of Convex Polytopes and Its Related Graphs.” Journal of Combinatorial Optimization 39(2): 334–50. https://doi.org/10.1007/s10878-019-00472-4.
Zhu, Enqiang, Andrej Taranenko, Zehui Shao, and Jin Xu. 2019. “On Graphs with the Maximum Edge Metric Dimension.” Discrete Applied Mathematics 257: 317–24. https://doi.org/10.1016/j.dam.2018.08.031.
Downloads
Published
Issue
Section
License
Copyright (c) 2026 Malaysian Journal of Science (MJS)
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
Transfer of Copyrights
- In the event of publication of the manuscript entitled [INSERT MANUSCRIPT TITLE AND REF NO.] in the Malaysian Journal of Science, I hereby transfer copyrights of the manuscript title, abstract and contents to the Malaysian Journal of Science and the Faculty of Science, University of Malaya (as the publisher) for the full legal term of copyright and any renewals thereof throughout the world in any format, and any media for communication.
Conditions of Publication
- I hereby state that this manuscript to be published is an original work, unpublished in any form prior and I have obtained the necessary permission for the reproduction (or am the owner) of any images, illustrations, tables, charts, figures, maps, photographs and other visual materials of whom the copyrights is owned by a third party.
- This manuscript contains no statements that are contradictory to the relevant local and international laws or that infringes on the rights of others.
- I agree to indemnify the Malaysian Journal of Science and the Faculty of Science, University of Malaya (as the publisher) in the event of any claims that arise in regards to the above conditions and assume full liability on the published manuscript.
Reviewer’s Responsibilities
- Reviewers must treat the manuscripts received for reviewing process as confidential. It must not be shown or discussed with others without the authorization from the editor of MJS.
- Reviewers assigned must not have conflicts of interest with respect to the original work, the authors of the article or the research funding.
- Reviewers should judge or evaluate the manuscripts objective as possible. The feedback from the reviewers should be express clearly with supporting arguments.
- If the assigned reviewer considers themselves not able to complete the review of the manuscript, they must communicate with the editor, so that the manuscript could be sent to another suitable reviewer.
Copyright: Rights of the Author(s)
- Effective 2007, it will become the policy of the Malaysian Journal of Science (published by the Faculty of Science, University of Malaya) to obtain copyrights of all manuscripts published. This is to facilitate:
- Protection against copyright infringement of the manuscript through copyright breaches or piracy.
- Timely handling of reproduction requests from authorized third parties that are addressed directly to the Faculty of Science, University of Malaya.
- As the author, you may publish the fore-mentioned manuscript, whole or any part thereof, provided acknowledgement regarding copyright notice and reference to first publication in the Malaysian Journal of Science and Faculty of Science, University of Malaya (as the publishers) are given. You may produce copies of your manuscript, whole or any part thereof, for teaching purposes or to be provided, on individual basis, to fellow researchers.
- You may include the fore-mentioned manuscript, whole or any part thereof, electronically on a secure network at your affiliated institution, provided acknowledgement regarding copyright notice and reference to first publication in the Malaysian Journal of Science and Faculty of Science, University of Malaya (as the publishers) are given.
- You may include the fore-mentioned manuscript, whole or any part thereof, on the World Wide Web, provided acknowledgement regarding copyright notice and reference to first publication in the Malaysian Journal of Science and Faculty of Science, University of Malaya (as the publishers) are given.
- In the event that your manuscript, whole or any part thereof, has been requested to be reproduced, for any purpose or in any form approved by the Malaysian Journal of Science and Faculty of Science, University of Malaya (as the publishers), you will be informed. It is requested that any changes to your contact details (especially e-mail addresses) are made known.
Copyright: Role and responsibility of the Author(s)
- In the event of the manuscript to be published in the Malaysian Journal of Science contains materials copyrighted to others prior, it is the responsibility of current author(s) to obtain written permission from the copyright owner or owners.
- This written permission should be submitted with the proof-copy of the manuscript to be published in the Malaysian Journal of Science
Licensing Policy
Malaysian Journal of Science is an open-access journal that follows the Creative Commons Attribution-Non-commercial 4.0 International License (CC BY-NC 4.0)
CC BY – NC 4.0: Under this licence, the reusers to distribute, remix, alter, and build upon the content in any media or format for non-commercial purposes only, as long as proper acknowledgement is given to the authors of the original work. Please take the time to read the whole licence agreement (https://creativecommons.org/licenses/by-nc/4.0/legalcode ).
