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 89
- Downloads 0
A Survey of Various Frameworks and Solutions in all Branches of Digital Forensics with a Focus on Cloud Forensics
Digital forensics is a class of forensic science interested with the use of digital information produced, stored and transmitted by various digital devices as source of evidence in investigations and legal proceedings. D...
Cryptanalysis of An Advanced Authentication Scheme
In this paper we study a scheme for making cryptanalysis and security improvement. This protocol by Song, is a password authentication protocol using smart card. We note that this protocol has been shown to be prone to t...
The Role of Camera Convergence in Stereoscopic Video See-through Augmented Reality Displays
In the realm of wearable augmented reality (AR) systems, stereoscopic video see-through displays raise issues related to the user’s perception of the three-dimensional space. This paper seeks to put forward few considera...
Face Behavior Recognition Through Support Vector Machines
Communication between computers and humans has grown to be a major field of research. Facial Behavior Recognition through computer algorithms is a motivating and difficult field of research for establishing emotional int...
Formalization of Learning Patterns Through SNKA
The Learning patterns found among the learners community is steadily progressing towards the digitalized world. The learning patterns arise from acquiring and sharing knowledge. More impact is found on the usage of knowl...