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 76
- Downloads 0
An Overview on Underutilized Wild Edible Plants as a Source of Alternative Nutrition
Ensuring a stable, hygienic, as well as nutritious food supplies for the poor and undernourished people of emerging economies is a serious concern today. Scarcity, high cost, and intermittent supply of healthy food have...
NAFDAC INFORMATION SYSTEM FOR PRODUCT REGISTRATION
The study aims at designing an information system to enhance the registration of products with ease and effectiveness for NAFDAC(National Agency for food and drugs Administration and control) as a case study. This study...
An Overview, Origins, Uses, and Difficulties of IoT
The Internet of Things (IoT) is quickly expanding nowadays. In the near future, billions of gadgets are likely to be linked. Smart and sensing devices have had an influence on Big Data by generating and collecting large...
The New Topology of Multi Level Inverter with Minimum of Switches
A new multilayer inverter topology is proposed in this study. The cascaded feature is used in this innovative topology. In addition to the isolated DC sources seen in Cascaded H-bridge. The clamping diode in Diode and th...
A Study on Ergonomics for Employee Wellness
The nature of work in modern society is changing rapidly, and competition in the job market is getting more intense. This requires competence from workers and demands them to update their knowledge, skills, and attitudes...