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 72
- Downloads 0
Using Artificial Intelligence Approaches to Categorise Lecture Notes
Lecture materials cover a broad variety of documents ranging from e-books, lecture notes, handouts, research papers and lab reports amongst others. Downloaded from the Internet, these documents generally go in the Downlo...
Scrum Method Implementation in a Software Development Project Management
To maximize the performance, companies conduct a variety of ways to increase the business profit. The work management between one company and the other company is different, so the differences in the management may cause...
Framework for Managing Uncertain Distributed Categorical Data
In recent years, data has become uncertain due to the flourishing advanced technologies that participate continuously and increasingly in producing large amounts of incomplete data. Often, many modern applications where...
Modelling of Thermal Storage in Damaged Composite Structures using Time Displaced Gradient Field Technique (TDGF)
This paper presents a new approach to composite surface characterization using Gradient Field time displacement. The new technique employs calculation of thermally charged regions within a composite structure as a result...
Separability Detection Cooperative Particle Swarm Optimizer based on Covariance Matrix Adaptation
The particle swarm optimizer (PSO) is a population-based optimization technique that can be widely utilized to many applications. The cooperative particle swarm optimization (CPSO) applies cooperative behavior to i...