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, w...

Full description

Main Authors: Abed, S.A., Rais, H.M.
Format: Article
Institution: Universiti Teknologi Petronas
Record Id / ISBN-0: utp-eprints.19724 /
Published: IOS Press 2017
Online Access: https://www.scopus.com/inward/record.uri?eid=2-s2.0-85029897973&doi=10.3233%2fJIFS-17398&partnerID=40&md5=4d739c0c7fb803691ad68857b82cfaeb
http://eprints.utp.edu.my/19724/
Tags: Add Tag
No Tags, Be the first to tag this record!
id utp-eprints.19724
recordtype eprints
spelling utp-eprints.197242018-04-20T07:34:10Z Hybrid bat algorithm for minimum dominating set problem Abed, S.A. Rais, H.M. 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. IOS Press 2017 Article PeerReviewed https://www.scopus.com/inward/record.uri?eid=2-s2.0-85029897973&doi=10.3233%2fJIFS-17398&partnerID=40&md5=4d739c0c7fb803691ad68857b82cfaeb Abed, S.A. and Rais, H.M. (2017) Hybrid bat algorithm for minimum dominating set problem. Journal of Intelligent and Fuzzy Systems, 33 (4). pp. 2329-2339. http://eprints.utp.edu.my/19724/
institution Universiti Teknologi Petronas
collection UTP Institutional Repository
description 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.
format Article
author Abed, S.A.
Rais, H.M.
spellingShingle Abed, S.A.
Rais, H.M.
Hybrid bat algorithm for minimum dominating set problem
author_sort Abed, S.A.
title Hybrid bat algorithm for minimum dominating set problem
title_short Hybrid bat algorithm for minimum dominating set problem
title_full Hybrid bat algorithm for minimum dominating set problem
title_fullStr Hybrid bat algorithm for minimum dominating set problem
title_full_unstemmed Hybrid bat algorithm for minimum dominating set problem
title_sort hybrid bat algorithm for minimum dominating set problem
publisher IOS Press
publishDate 2017
url https://www.scopus.com/inward/record.uri?eid=2-s2.0-85029897973&doi=10.3233%2fJIFS-17398&partnerID=40&md5=4d739c0c7fb803691ad68857b82cfaeb
http://eprints.utp.edu.my/19724/
_version_ 1741196252723281920
score 11.62408

Similar Items