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 96
- Downloads 0
Time and Motion Study Methods for Manufacturing a Pump
The purpose of the study was to compare conventional time study method and MOST analysis on oil pump assembly in a manufacturing company. The results showed that the time study resulted in 0.239 minutes and MOST resulted...
An Induction Generator based AC/DC Hybrid Electric Power Generation System for Additional Electrically Powered Airliner
For an additional aircraft power system, both AC and DC power having high voltage levels are required. with various flight loads. This paper introduces an induction generator based on AC / DC hybrid MEA power generation...
Heuristic Walkthrough Usability Evaluation of Electronic Health Record with a Proposed Security Architecture
There currently appears to be concerted efforts at national (HSE) Regional (EU) and international (WHO) level to promote the replacement of paper-based record systems with electronic health record systems (EHR) for impro...
Precinct Vaticinator on Social-Media using Machine Learning Techniques
Precinct vaticinator of users from online social media brings considerable research these days. Automatic recognition of precinct related with or referenced in records has been investigated for decades. As a standout amo...
Laboratory Review for Stabilization of Soil in Kashmir VALLEY by Using Surkhi and Ceramic Tile Waste
Clay soil has been identified as a concern all around the world due to its swelling and shrinking qualities when it comes into touch with water. The load characteristics of soil are particularly low due to this clay feat...