Hybrid ant colony optimization algorithm with binary gray wolf optimization for detour metric dimension and bi-metric dimension problem

Articles in Press

Document Type : Original paper

Authors

1 Department of Mathematics, Faculty of Science and Data Analytics, Institut Teknologi Sepuluh Nopember, Surabaya, Indonesia

2 Faculty of Engineering, Universitas Kadiri, Kediri, Indonesia

Abstract

In this work, two class NP-hard optimization problems on the graph are discussed: the detour metric dimension and the bi-metric dimension. Both are used in many distinct areas, as well as pattern recognition, keeping track of the movement of robots on a network, and reviewing the structural properties of chemical structures. The metric dimension dim(G) of graph G is the minimum number of vertices such that every vertex of G is uniquely assigned by its vector of distances to the selected vertices. This concept was expanded into the detour metric dimension Dβ(G) and the bi-metric dimension βb(G) by considering the detour distance of two vertices. A computational approach is needed to solve these two problems on large graphs. In this research, we propose the BGWO algorithm to determine the metric dimension of some generalized antiprism graphs. In addition, we develop a probabilistic-based metaheuristic algorithm, namely ant colony optimization, to find the detour distance and then modify the binary gray wolf optimization (BGWO) algorithm to solve the detour metric dimension and the bi-metric dimension on some families of graphs. The simulation shows that the BGWO algorithm gives better results for the generalized antiprism graphs. Also, the hybrid ACO-BGWO algorithm gives the same detour dimension result as in the literature. We show that the bi-metric dimension of the generalized antiprism graph is the same as its metric dimension.

Keywords

Main Subjects

References

[1] S. Akhter and R. Farooq, Metric dimension of fullerene graphs., Electron. J. Graph Theory Appl. 7 (2019), no. 1, 91–103.
https://doi.org/10.5614/ejgta.2019.7.1.7
[2] J. Bensmail, F.M. Inerney, and N. Nisse, Metric dimension: From graphs to oriented graphs, Discrete Appl. Math. 323 (2022), 28–42.  https://doi.org/10.1016/j.entcs.2019.08.011
[3] G. Chartrand, L. Eroh, M.A. Johnson, and O.R. Oellermann, Resolvability in graphs and the metric dimension of a graph, Discrete Appl. Math. 105 (2000), no. 1-3, 99–113.  https://doi.org/10.1016/S0166-218X(00)00198-0
[4] G. Chartrand, L. Eroh, M.A. Johnson, and O.R. Oellermann, Resolvability in graphs and the metric dimension of a graph, Discrete Appl. Math. 105 (2000), no. 1-3, 99–113.  https://doi.org/10.1016/S0166-218X(00)00198-0
[5] K. Chau and S. Gosselin, The metric dimension of circulant graphs and their  Cartesian products, Opuscula Math. 37 (2017), no. 4, 509–534. http://dx.doi.org/10.7494/OpMath.2017.37.4.509
[6] V.K. Devi and K. Marimuthu, A new encryption technique using detour metric dimension, J. Infor. Math. Sci. 9 (2017), no. 3, 949–955.  https://doi.org/10.26713/jims.v9i3.1015
[7] M. Dorigo, M. Birattari, and T. Stutzle, Ant colony optimization: Artificial ants  as a computational intelligence technique, IEEE Comput. Intell. Mag. 1 (2006), no. 4, Article ID: 28.
[8] F. El Asri, C. Tajani, and H. Fakhouri, A combined ant colony optimization with levy flight mechanism for the probabilistic traveling salesman problem with deadlines, Math. Model. Comput. 11 (2024), no. 1, 290–299. https://doi.org/10.23939/mmc2024.01.290
[9] E. Emary, H.M. Zawbaa, and A.E. Hassanien, Binary grey wolf optimization approaches for feature selection,  Neurocomputing 172 (2016), 371–381.  https://doi.org/10.1016/j.neucom.2015.06.083
[10] L. Eroh, C.X. Kang, and E. Yi, On metric dimension of functigraphs, Discrete Math. Algorithms Appl. 5 (2013), no. 04, Article ID: 1250060.  https://doi.org/10.1142/S1793830912500607
[11] M. Fehr, S. Gosselin, and O.R. Oellermann, The metric dimension of Cayley digraphs, Discrete Math. 306 (2006), no. 1, 31–41.  https://doi.org/10.1016/j.disc.2005.09.015
[12] M. Feng and K. Wang, On the metric dimension of bilinear forms graphs, Discrete Math. 312 (2012), no. 6, 1266–1268.
https://doi.org/10.1016/j.disc.2011.11.020
[13] M. Feng, M. Xu, and K. Wang, On the metric dimension of line graphs, Discrete Appl. Math. 161 (2013), no. 6, 802–805. https://doi.org/10.1016/j.dam.2012.10.018
[14] J. Guo, K. Wang, and F. Li, Metric dimension of some distance-regular graphs, J. Comb. Optim. 26 (2013), no. 1, 190–197.  https://doi.org/10.1007/s10878-012-9459-x
[15] F. Harrary and R.A. Melter, On the metric dimension of a graph, Ars Combin. 2 (1976), 191–195.
[16] J.T. Hedetniemi, S.T. Hedetniemi, R.C. Laskar, and M. Mulder, The 2-dimension of a tree, Commun. Comb. Optim. 5 (2020), no. 1, 69–81.  https://doi.org/10.22049/cco.2019.26495.1119
[17] H. Hendy, M.I. Irawan, I. Mukhlash, and S. Setumin, A bibliometric analysis of metaheuristic research and its applications, Regist.: J. Ilm. Teknol. Sist. Inf. 9  (2023), no. 1, 1–17.  http://doi.org/10.26594/register.v9i1.2675
[18] C. Hernando, M. Mora, I.M. Pelayo, C. Seara, J. Cáceres, and M.L. Puertas, On  the metric dimension of some families of graphs, Electron. Notes Discrete Math.  22 (2005), 129–133.  https://doi.org/10.1016/j.endm.2005.06.023
[19] M. Imran, A.Q. Baig, S.A.U.H. Bokhary, and I. Javaid, On the metric dimension of circulant graphs, Appl. Math. Lett. 25 (2012), no. 3, 320–325.  https://doi.org/10.1016/j.aml.2011.09.008
[20] M. Imran, M.K. Siddiqui, and R. Naeem, On the metric dimension of generalized petersen multigraphs, IEEE access 6 (2018), 74328–74338.  https://doi.org/10.1109/ACCESS.2018.2883556
[21] S. Imran, M.K. Siddiqui, M. Imran, M. Hussain, H.M. Bilal, I.Z. Cheema,  A. Tabraiz, and Z. Saleem, Computing the metric dimension of gear graphs,  Symmetry 10 (2018), no. 6, Article ID: 209.  https://doi.org/10.3390/sym10060209
[22] T. Jayabarathi, T. Raghunathan, B.R. Adarsh, and P.N. Suganthan, Economic dispatch using hybrid grey wolf optimizer, Energy 111 (2016), 630–641.  https://doi.org/10.1016/j.energy.2016.05.105
[23] J. Kratica, V. Kovačević-Vujčić, and M. Čangalović, Computing the metric dimension of graphs by genetic algorithms, Comput. Optim. Appl. 44 (2009), no. 2,  343–361. https://doi.org/10.1007/s10589-007-9154-5
[24] J.B. Liu, M.F. Nadeem, H.M.A. Siddiqui, and W. Nazir, Computing metric dimension of certain families of toeplitz graphs, IEEE Access 7 (2019), 126734–126741.  https://doi.org/10.1109/ACCESS.2019.2938579
[25] S. Mirjalili, S.M. Mirjalili, and A. Lewis, Grey wolf optimizer, Adv. Eng. Softw. 69 (2014), 46–61. https://doi.org/10.1016/j.advengsoft.2013.12.007
[26] N. Mladenović, J. Kratica, V. Kovačević-Vujčić, and M. Čangalović, Variable neighborhood search for metric dimension and minimal doubly resolving set problems, European J. Oper. Res. 220 (2012), no. 2, 328–337. https://doi.org/10.1016/j.ejor.2012.02.019
[27] B. Mohamed and M. Amin, A hybrid optimization algorithms for solving metric dimension problem, International Journal on Applications of Graph Theory in Wireless Ad hoc Networks and Sensor Networks (GRAPH-HOC) 15 (2023),
no. 1/2, 1–10.  https://doi.org/10.5121/jgraphoc.2023.15201
[28] B. Mohamed, L. Mohaisen, and M. Amin, Binary equilibrium optimization algorithm for computing connected domination metric dimension problem, Sci. Program. 2022 (2022), no. 1, Article ID: 6076369. https://doi.org/10.1155/2022/6076369
[29] D.T. Murdiansyah and Adiwijaya, Computing the metric dimension of hypercube graphs by particle swarm optimization algorithms, Recent Advances on Soft Computing and Data Mining (Cham) (T. Herawan, R. Ghazali, N.M. Nawi, and M.M. Deris, eds.), Springer International Publishing, 2017, pp. 171–178.
[30] R. Pal, M. Saraswat, S. Kumar, A. Nayyar, and P.K. Rajput, Energy efficient multi-criterion binary grey wolf optimizer based clustering for heterogeneous wireless sensor networks, Soft Comput. 28 (2024), no. 4, 3251–3265. https://doi.org/10.1007/s00500-023-09316-0
[31] A. Raghavendra, B. Sooryanarayana, and C. Hegde, Bi-metric dimension of graphs, British J. Math. & Comput. Sci. 4 (2014), no. 18, Article ID: 2699.
[32] R.R. Rajammal, S. Mirjalili, G. Ekambaram, and N. Palanisamy, Binary grey wolf optimizer with mutation and adaptive k-nearest neighbour for feature selection in parkinson’s disease diagnosis, Knowledge-Based Systems 246 (2022), Article ID: 108701.  https://doi.org/10.1016/j.knosys.2022.108701
[33] S. Rehman, M. Imran, and I. Javaid, On the metric dimension of arithmetic graph of a composite number, Symmetry 12 (2020), no. 4, Article ID: 607.  https://doi.org/10.3390/sym12040607
[34] S.W. Saputro, On the metric dimension of biregular graph, J. Inf. Process. 25 (2017), 634–638. https://doi.org/10.2197/ipsjjip.25.634
[35] Z. Shao, S.M. Sheikholeslami, Pu Wu, and J.B. Liu, The metric dimension of  some generalized petersen graphs, Discrete Dyn. Nat. Soc. 2018 (2018), no. 1,  Article ID: 4531958.  https://doi.org/10.1155/2018/4531958
[36] P. Slater, Leaves of trees, Proc. 6th Southeastern Conf. on Combinatorics, Graph Theory, and Computing, Congr. Numer., vol. 14, Elsevier, 1975, pp. 549–559.
[37] B. Sooryanarayana, S Kunikullaya, and N.N. Swamy, Metric dimension of generalized wheels, Arab J. Math. Sci. 25 (2019), no. 2, 131–144.
[38] T. Vetrík, The metric dimension of circulant graphs, Canad. Math. Bull. 60 (2017), no. 1, 206–216. https://doi.org/10.4153/CMB-2016-048-1.
[39] T. Vetrík, On the metric dimension of directed and undirected circulant graphs,  Discuss. Math. Graph Theory 40 (2019), no. 1, 67–76.  http://dx.doi.org/10.7151/dmgt.2110
[40] J. Wu, L. Wang, and W. Yang, Learning to compute the metric dimension of graphs, Appl. Math. Comput. 432 (2022), Article ID: 127350.  https://doi.org/10.1016/j.amc.2022.127350
Communications in Combinatorics and Optimization

Articles in Press, Accepted Manuscript
Available Online from 25 April 2025

Files

Share

How to cite

Statistics