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 78
- Downloads 0
An Analysis of Soil Stability Techniques
Soil Steadiness is procedure of augmenting bearing capacity of soil by improving shear asset characteristics of soil. When soil available for building is unsuitable for carrying structural loads, it is needed. Soils...
Collaborative Load Balancing and Effective Channel Allocation for Cluster-Based MANETs
Mobile ad hoc network is a wireless network group of mobile devices having no infrastructure. Load balancing is an important problem in such networks due to dynamic topology of the nodes. Many protocols are developed to...
Determining Long-Term Stability in Environmental Science
A person's or a community's related emissions is an indication of the number of energy needed to produce their commodities. However, data shows that it only lasts for a short period of time. There has been much criticism...
IOT Based Smart Greenhouse Automation Using Arduino
Greenhouse Automation System is the technical approach in which the farmers in the rural areas will be benefitted by automatic monitoring and control of greenhouse environment. It replaces the direct supervision of the h...
An Overview of Device-To-Device Communication in Cellular Networks
Gadget to-Device (D2D) correspondence was first recommended as another worldview for further developing organization execution in cell organizations. New use-cases for D2D correspondences in cell networks have arisen bec...