Hybrid bat algorithm for minimum dominating set problem

Graph domination is one of the NP-Complete problems that cannot be solved exactly in polynomial time. Hence, we propose a stochastic approach to tackle the minimum dominating set problem (MDS). The main aim of MDS is to find the minimum number of nodes that covers all other nodes in a graph. Thus, we present the problem in binary sequence to activate a node to be a dominator by setting it to the value of 1, or deactivate it by assigning its value to 0. In this paper, the stochastic search represented by hybrid swarm intelligence algorithm to find the smallest set of nodes that dominate the graph. This method uses population-based approach called bat algorithm (BA) which explore a wide area of the search space, thus it is capable in the diversification procedure. However, population-based algorithms are not good in exploiting the search space in comparison to single-solution based methods, therefore we included simulated annealing (SA) algorithm to balance between exploitation and exploration in order to reach a best possible solution. Our proposed method was experimented on benchmark datasets, which yielded results comparable to the state-of-the-art MDS methods. It can be concluded that the proposed method is an effective solution for MDS problem. © 2017 - IOS Press and the authors. All rights reserved.