TARU PUBLICATIONS
Journal of Information and Optimization Sciences cover

Journal of Information and Optimization Sciences

(Since 1980)
Hybrid ·Peer-reviewed·ISSN (Online): 2169-0103·ISSN (Print): 0252-2667

WoS  JIF 2026 : 0.4 (Q4)

Powered by:Powered by

Monthly Journal: Publishes theoretical and applied research on topics in information and optimization sciences.

Issues up to 2022 co-published with and available at:Taylor & Francis
submissions@tarupublications.com
Taru Online First Current IssueSpecial IssuesBrowse all Issues
Journal of Information and Optimization Sciences
Open Access Research Article

Optimizing minimum dominating set using an enhanced binary whale algorithm

, *

* Corresponding author · click or hover a name for details

pp. 887–905Vol. 47Issue 3March 2026DOI: 10.47974/JIOS-1583XML
Received:
10 May 2023
Published Online:
15 Jul 2025
Article type:
Research Article
Language:
EN
Article no.:
JIOS-1583
Pages:
887–905

Abstract

The Whale Optimization Algorithm (WOA) is an innovative metaheuristic inspired by the social hunting behavior of humpback whales. This paper presents a binary version of the WOA applied to the Minimum Dominating Set (MDS) problem, a challenging combinatorial optimization problem known to be NP-hard. However, the WOA suffers from premature convergence, potentially causing the algorithm to become trapped in local optima and fail to reach the global optimum. To address this issue, the paper introduces an enhanced version of WOA called the Local Search Optimization Binary Whale ( Lobw), which incorporates a Local Search technique to improve exploitation ability and prevent the algorithm from getting stuck in local optima. The Lobw algorithm is evaluated on several benchmark datasets, demonstrating its promising performance in terms of solution quality and stability compared to other metaheuristic algorithms. The source code of the  Lobw algorithm and the datasets used in the experiments can be accessed via the following link: https://github.com/elkacem/LOBW-for-MDS.

Keywords

Minimum dominating setMetaheuristicsWhale optimization algorithmLocal search

Subject Classifications

05C6990C5990C27

References

[1] T. W. Haynes, S. T. Hedetniemi, and P. J. Slater, Fundamentals of Domination in Graphs. Boca Raton, FL, USA: CRC Press (2013).
[2] F. Dai and J. Wu, “An extended localized algorithm for connected dominating set formation in ad hoc wireless networks,” IEEE Transactions on Parallel and Distributed Systems, vol. 15, no. 10, pp. 908–920 (Oct. 2004).
[3] J. Blum, M. Ding, A. Thaeler, and X. Cheng, “Connected dominating set in sensor networks and MANETs,” in Handbook of Combinatorial Optimization, D.-Z. Du and P. Pardalos, Eds. Boston, MA, USA: Springer, pp. 329–369 (2004).
[4] C. Shen and T. Li, “Multi-document summarization via the minimum dominating set,” in Proc. 23rd Int. Conf. Computational Linguistics (COLING), Beijing, China, pp. 984–992 (2010).
[5] M. M. Daliri Khomami, A. Rezvanian, N. Bagherpour, and M. R. Meybodi, “Minimum positive influence dominating set and its application in influence maximization: A learning automata approach,” Applied Intelligence, vol. 48, no. 3, pp. 570–593 (Mar. 2018).
[6] D. Zhao, G. Xiao, Z. Wang, L. Wang, and L. Xu, “Minimum dominating set of multiplex networks: Definition, application, and identification,” IEEE Transactions on Systems, Man, and Cybernetics: Systems, vol. 51, no. 12, pp. 7823–7837 (Dec. 2021).
[7] S. Wuchty, “Controllability in protein interaction networks,” Proceedings of the National Academy of Sciences, vol. 111, no. 19, pp. 7156–7160 (May 2014).
[8] E. H. Houssein, A. Hamad, A. E. Hassanien, and A. A. Fahmy, “Epileptic detection based on whale optimization enhanced support vector machine,” Journal of Information and Optimization Sciences, vol. 40, no. 3, pp. 699–723 (2019), doi: 10.1080/02522667.2018.1453671.
[9] M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, vol. 174. San Francisco, CA, USA: W. H. Freeman (1979).
[10] Y. Iwata, “A faster algorithm for dominating set analyzed by the potential method,” in Proc. Int. Symp. Parameterized and Exact Computation, Zurich, Switzerland: Springer, pp. 41–54 (2011).
[11] E.-G. Talbi, Metaheuristics: From Design to Implementation. Hoboken, NJ, USA: John Wiley & Sons (2009).
[12] S. Kirkpatrick, C. D. Gelatt Jr., and M. P. Vecchi, “Optimization by simulated annealing,” Science, vol. 220, no. 4598, pp. 671–680 (May 1983).
[13] Z. W. Geem, J. H. Kim, and G. V. Loganathan, “A new heuristic optimization algorithm: Harmony search,” Simulation, vol. 76, no. 2, pp. 60–68 (Feb. 2001).
[14] A. K. Parekh, “Analysis of a greedy heuristic for finding small dominating sets in graphs,” Information Processing Letters, vol. 39, no. 5, pp. 237–240 (Mar. 1991).
[15] P.-J. Wan, K. M. Alzoubi, and O. Frieder, “A simple heuristic for minimum connected dominating set in graphs,” International Journal of Foundations of Computer Science, vol. 14, no. 2, pp. 323–333 (Apr. 2003).
[16] Y. Alkhalifah and R. L. Wainwright, “A genetic algorithm applied to graph problems involving subsets of vertices,” in Proc. 2004 Congress on Evolutionary Computation (CEC’04), vol. 1, Portland, OR, USA: IEEE, pp. 303–308 (2004).
[17] R. Misra and C. Mandal, “Minimum connected dominating set using a collaborative cover heuristic for ad hoc sensor networks,” IEEE Transactions on Parallel and Distributed Systems, vol. 21, no. 3, pp. 292–302 (Mar. 2009).
[18] L. A. Sanchis, “Experimental analysis of heuristic algorithms for the dominating set problem,” Algorithmica, vol. 33, no. 1, pp. 3–18 (Jan. 2002).
[19] M. Dorigo, M. Birattari, and T. Stützle, “Ant colony optimization,” IEEE Computational Intelligence Magazine, vol. 1, no. 4, pp. 28–39 (Nov. 2006).
[20] C. K. Ho, Y. P. Singh, and H. T. Ewe, “An enhanced ant colony optimization metaheuristic for the minimum dominating set problem,” Applied Artificial Intelligence, vol. 20, no. 10, pp. 881–903 (Oct. 2006).
[21] J. H. Holland, Adaptation in Natural and Artificial Systems: An Introductory Analysis with Applications to Biology, Control, and Artificial Intelligence. Cambridge, MA, USA: MIT Press (1992).
[22] A.-R. Hedar and R. Ismail, “Hybrid genetic algorithm for minimum dominating set problem,” in Proc. Int. Conf. Computational Science and Its Applications (ICCSA), Fukuoka, Japan: Springer, pp. 457–467 (2010).
[23] A.-R. Hedar and R. Ismail, “Simulated annealing with stochastic local search for minimum dominating set problem,” International Journal of Machine Learning and Cybernetics, vol. 3, no. 2, pp. 97–109 (Apr. 2012).
[24] S. A. Abed, H. M. Rais, J. Watada, and N. R. Sabar, “A hybrid local search algorithm for minimum dominating set problems,” Engineering Applications of Artificial Intelligence, vol. 114, p. 105053 (Aug. 2022).
[25] S. Mirjalili and A. Lewis, “The whale optimization algorithm,” Advances in Engineering Software, vol. 95, pp. 51–67 (May 2016).
[26] B. Chen, W. Zeng, Y. Lin, and D. Zhang, “A new local search-based multiobjective optimization algorithm,” IEEE Transactions on Evolutionary Computation, vol. 19, no. 1, pp. 50–73 (Feb. 2015).
[27] C. Bettstetter, “On the minimum node degree and connectivity of a wireless multihop network,” in Proc. 3rd ACM Int. Symp. Mobile Ad Hoc Networking & Computing (MobiHoc), Lausanne, Switzerland, pp. 80–91 (2002).
[28] J. Demšar, “Statistical comparisons of classifiers over multiple data sets,” Journal of Machine Learning Research, vol. 7, no. 1, pp. 1–30 (Jan. 2006).
[29] A. Benavoli, G. Corani, and F. Mangili, “Should we really use post-hoc tests based on mean-ranks?,” Journal of Machine Learning Research, vol. 17, no. 1, pp. 152–161 (Jan. 2016).

Views: 168Downloads: 90Citations: 0