A Comparative Study of Cat Swarm Algorithm for Graph Coloring Problem: Convergence Analysis and Performance Evaluation
Journal Title: International Journal of Innovative Research in Computer Science and Technology - Year 2024, Vol 12, Issue 4
Abstract
The Graph Coloring Problem (GCP) is a significant optimization challenge widely suitable to solve scheduling problems. Its goal is to specify the minimum colors (k) required to color a graph properly. Due to its NP-completeness, exact algorithms become impractical for graphs exceeding 100 vertices. As a result, approximation algorithms have gained prominence for tackling large-scale instances. In this context, the Cat Swarm algorithm, a novel population-based metaheuristic in the domain of swarm intelligence, has demonstrated promising convergence properties compared to other population-based algorithms. This research focuses on designing and implementing the Cat Swarm algorithm to address the GCP. By conducting a comparative study with established algorithms, our investigation revolves around quantifying the minimum value of k required by the Cat Swarm algorithm for each graph instance. The evaluation metrics include the algorithm's running time in seconds, success rate, and the mean count of iterations or assessments required to reach a goal.
Authors and Affiliations
Ayesha Saeed, Ali Husnain, Anam Zahoor and Rashad Mehmood Gondal
Keywords
Related Articles
- EP ID EP744912
- DOI 10.55524/ijircst.2024.12.4.1
- Views 37
- Downloads 0
A Review on Machine Learning and Its Applications
Learning is the most important aspect of human intellect and the most fundamental method of acquiring information. Machine learning is the most basic method for making a machine intelligent. Application Data has grown in...
Regression and Classification Model Based Predictive Maintenance of Aircrafts Using Neural Network
One of the key objectives of today's businesses and mills is to predict machine problems. Failures must be avoided, because downtimes represent expensive expenses and a loss of productivity. This is why the number of rem...
Comparison of Design Response Spectra in SNI 1726:2012 and SNI 1726:2019
At the end of 2019, the Indonesian National Standards Agency issued new regulations regarding procedures for earthquake resistance planning in building and non-building structures or SNI 1726:2019. The existence of new r...
The Brief study on the Human Nail
A nail is a structure which is not a bone made up of different composition than skin tissue like keratin which is also found in hair and this is also shown as an outer layer of skin for protection. Nail used to protect f...
A Comparative Study of Cat Swarm Algorithm for Graph Coloring Problem: Convergence Analysis and Performance Evaluation
The Graph Coloring Problem (GCP) is a significant optimization challenge widely suitable to solve scheduling problems. Its goal is to specify the minimum colors (k) required to color a graph properly. Due to its NP-compl...