Chemical Reaction Optimization for Minimum Weight Dominating Set
Dominating set of a graph can be defined as the set of vertices that can cover all other vertices of the graph. The minimum weight dominating set (MWDS) is the minimum number of vertices in the dominating set with minimum total weight. In recent times, the chemical reaction optimization algorithm (C...
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Wiley
2023-01-01
|
| Series: | Applied Computational Intelligence and Soft Computing |
| Online Access: | http://dx.doi.org/10.1155/2023/9640807 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1849699172672864256 |
|---|---|
| author | A. Pritam Khan Boni B. Md. Rafiqul Islam |
| author_facet | A. Pritam Khan Boni B. Md. Rafiqul Islam |
| author_sort | A. Pritam Khan Boni |
| collection | DOAJ |
| description | Dominating set of a graph can be defined as the set of vertices that can cover all other vertices of the graph. The minimum weight dominating set (MWDS) is the minimum number of vertices in the dominating set with minimum total weight. In recent times, the chemical reaction optimization algorithm (CRO) has shown its supremacy in solving these types of problems. Therefore in this paper, a novel approach based on CRO has been proposed to solve the MWDS problem. The proposed method uses a repair-based technique to generate a molecule. To make the solution feasible by covering all vertices and to get better results, three supporting operators are implemented along with the CRO operators. Besides this, two repair operators are introduced. In the first repair operator, the searching procedure works based on the scaling properties of vertices, and the second one is a unique method for eliminating common neighbors of vertices of the dominating set. The performance of the proposed method is better than any other existing related algorithms. The performance is measured from different graphs of the benchmark datasets. It can be mentioned that the proposed method takes minimal running time to obtain the minimum weight compared to other benchmark methods. |
| format | Article |
| id | doaj-art-2bdb47affbfe4607af886bd0317c627c |
| institution | DOAJ |
| issn | 1687-9732 |
| language | English |
| publishDate | 2023-01-01 |
| publisher | Wiley |
| record_format | Article |
| series | Applied Computational Intelligence and Soft Computing |
| spelling | doaj-art-2bdb47affbfe4607af886bd0317c627c2025-08-20T03:18:41ZengWileyApplied Computational Intelligence and Soft Computing1687-97322023-01-01202310.1155/2023/9640807Chemical Reaction Optimization for Minimum Weight Dominating SetA. Pritam Khan Boni0B. Md. Rafiqul Islam1Khulna UniversityKhulna UniversityDominating set of a graph can be defined as the set of vertices that can cover all other vertices of the graph. The minimum weight dominating set (MWDS) is the minimum number of vertices in the dominating set with minimum total weight. In recent times, the chemical reaction optimization algorithm (CRO) has shown its supremacy in solving these types of problems. Therefore in this paper, a novel approach based on CRO has been proposed to solve the MWDS problem. The proposed method uses a repair-based technique to generate a molecule. To make the solution feasible by covering all vertices and to get better results, three supporting operators are implemented along with the CRO operators. Besides this, two repair operators are introduced. In the first repair operator, the searching procedure works based on the scaling properties of vertices, and the second one is a unique method for eliminating common neighbors of vertices of the dominating set. The performance of the proposed method is better than any other existing related algorithms. The performance is measured from different graphs of the benchmark datasets. It can be mentioned that the proposed method takes minimal running time to obtain the minimum weight compared to other benchmark methods.http://dx.doi.org/10.1155/2023/9640807 |
| spellingShingle | A. Pritam Khan Boni B. Md. Rafiqul Islam Chemical Reaction Optimization for Minimum Weight Dominating Set Applied Computational Intelligence and Soft Computing |
| title | Chemical Reaction Optimization for Minimum Weight Dominating Set |
| title_full | Chemical Reaction Optimization for Minimum Weight Dominating Set |
| title_fullStr | Chemical Reaction Optimization for Minimum Weight Dominating Set |
| title_full_unstemmed | Chemical Reaction Optimization for Minimum Weight Dominating Set |
| title_short | Chemical Reaction Optimization for Minimum Weight Dominating Set |
| title_sort | chemical reaction optimization for minimum weight dominating set |
| url | http://dx.doi.org/10.1155/2023/9640807 |
| work_keys_str_mv | AT apritamkhanboni chemicalreactionoptimizationforminimumweightdominatingset AT bmdrafiqulislam chemicalreactionoptimizationforminimumweightdominatingset |