Chemical Reaction Optimization Algorithm to Find Maximum Independent Set in a Graph
Journal Title: International Journal of Advanced Computer Science & Applications - Year 2019, Vol 10, Issue 9
Abstract
Finding maximum independent set (MIS) in a graph is considered one of the fundamental problems in the computer science field, where it can be used to provide solutions for various real life applications. For example, it can be used to provide solutions in scheduling and prioritization problems. Unfortunately, this problem is one of the NP-problems of computer science, which limit its usage in providing solution for such problems with large sizes. This leads the scientists to find a way to provide solutions of such problems using fast algorithms to provide some near optimal solutions. One of the techniques used to provide solutions is to use metaheuristic algorithms. In this paper, a metaheuristic algorithm based on Chemical Reaction Optimization (CRO) is applied with various techniques to find MIS for application represented by a graph. The suggested CRO algorithm achieves accuracy percentages that reach 100% in some cases. This variation depends on the overall structure of the graph along with the picked parameters and colliding molecule selection criteria during the reaction operations of the CRO algorithm.
Authors and Affiliations
Mohammad A. Asmaran, Ahmad A. Sharieh, Basel A. Mahafzah
Keywords
Related Articles
- EP ID EP645807
- DOI 10.14569/IJACSA.2019.0100912
- Views 122
- Downloads 0
Identification and Nonlinear PID Control of Hammerstein Model using Polynomial Structures
In this paper, a new nonlinear discrete-time PID is proposed to control Hammerstein model. This model is composed by a static nonlinearity gain associated to a linear dynamic sub-system. Nonlinear polynomial structures a...
Insight to Research Progress on Secure Routing in Wireless Ad hoc Network
Wireless Ad hoc Network offers a cost effective communication to the users free from any infrastructural dependencies. It is characterized by decentralized architecture, mobile nodes, dynamic topology, etc. that makes th...
Improved QO-STBC OFDM System Using Null Interference Elimination
The quasi-orthogonal space time block coding (QO-STBC) over orthogonal frequency division multiplexing (OFDM) is investigated. Traditionally, QO-STBC does not achieve full diversity since the detection matrix of QO-STBC...
Semi-Automatic Segmentation System for Syllables Extraction from Continuous Arabic Audio Signal
The paper describes a speaker independent segmentation system for breaking Arabic uttered sentences into its constituent syllables. The goal is to construct a database of acoustical Arabic syllables as a step towards a s...
EEG based Brain Alertness Monitoring by Statistical and Artificial Neural Network Approach
Since several work requires continuous alertness like efficient driving, learning, etc. efficient measurement of the alertness states through neural activity is a crucial challenge for the researchers. This work reports...