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 44
- Downloads 0
Review on Deep Learning, Machine Learning and its Application
In contemporary computer sciences, machine learning is one of the areas. To make machines intelligent, a lot of study has been done. Learning is a fundamental aspect of both computer and human behavior. For the same prob...
Predicting the Concrete Properties Using Machine Learning- A Step Towards Smart Infrastructure
The mechanical properties of concrete mixtures are of a great concern when engineers need to provide the estimation of the concrete strength in addition to forecast the behavior of innovative concrete types. Predicting s...
Computer Forensics Data Recovery Software: A Comparative Study
With the advancement of the information technology, computer has become more important for the people. Computer not only stores data but also increase the channels of storing data in digital devices like pen drive, hard...
Review Paper on Data Mining Techniques and Applications
Data mining is the process of extracting hidden and useful patterns and information from data. Data mining is a new technology that helps businesses to predict future trends and behaviors, allowing them to make proactive...
Ethylene Glycol: Kinetics of the Formation from Methanol–Formaldehyde Solutions
The mechanism and kinetics are developed for the initiated nonbranched-chain formation of ethylene glycol in methanol–formaldehyde solutions at formaldehyde concentrations of 0.1–3.1 mol dm–3 and temperatures of 373–473...