A Comparative Study of Cat Swarm Algorithm for Graph Coloring Problem: Convergence Analysis and Performance Evaluation

Ayesha Saeed; Ali Husnain; Anam Zahoor; Rashad Mehmood Gondal

doi:10.55524/ijircst.2024.12.4.1

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.

Keywords

Cat Swarm Optimization, Cat Swarm Algorithm, Graph Coloring, Graph Coloring Problem

References

1. H. Al-Omari and K. E. Sabri, "New graph coloring algorithms," American Journal of Mathematics and Statistics, vol. 2, no. 4, pp. 739-741, 2006. Available from: https://thescipub.com/pdf/jmssp.2006.439.441.pdf

2. H. Almara’beh and A. Suleiman, "Heuristic algorithm for graph coloring based on maximum independent set," Journal of Applied Computer Science & Mathematics, vol. 13, no. 6, pp. 19-23, 2012. Available from: https://www.jacsm.ro/view/?pid=13_3

3. R. Dorne and J. K. Hao, "A new genetic local search algorithm for graph coloring," in Parallel Problem Solving from Nature—PPSN V: 5th International Conference Amsterdam, The Netherlands September 27–30, 1998 Proceedings 5, vol. 5, Springer Berlin Heidelberg, 1998, pp. 745-754.D. Available from: https://doi.org/10.1007/BFb0056916

4. Bre1az, "New Methods to Color the Vertices of a Graph," Management Science/Operations Research, Communications of the ACM, vol. 22, no. 4, pp. page numbers, 1979. Available from: https://doi.org/10.1145/359094.359101

5. J. A. Torkestani, "A New Vertex Coloring Algorithm Based On Variable Action-Set Learning Automata," Computing and Informatics, vol. 29, pp. 447–466, Arak, Iran, 2010. Available from: https://www.researchgate.net/publication/220106403_A_New_Vertex_Coloring_Algorithm_Based_on_Variable_Aaction-Set_Learning_Automata

6. S. C. Chu, P. W. Tsai, and J. S. Pan, "Cat swarm optimization," in PRICAI 2006: Trends in Artificial Intelligence: 9th Pacific Rim International Conference on Artificial Intelligence Guilin, China, August 7-11, 2006 Proceedings 9, Springer Berlin Heidelberg, 2006, pp. 854-858. Available from: https://www.geeksforgeeks.org/cat-swarm-optimization/

7. L. Rouse and M. Albrandt, "A Touch of Color: Graph Coloring," Mini-Excursion 2. Available from: https://www.claytonschools.net/cms/lib/MO01000419/Centricity/Domain/241/ChromaticChapter.pdf

8. N. D. Bacarisas and J. P. T. Yusiong, "The Effect of Varying the Fitness Function on the Efficiency of the Cat Swarm Optimization algorithm in Solving the Graph Colouring Problem," Annals. Computer Science Series, vol. 9, 2011. Available from: https://www.sciencedirect.com/topics/computer-science/swarm-optimization-algorithm

9. M. Chiarandini and T. Stützle, "An application of iterated local search to graph coloring problem," in Proc. Computational Symposium on Graph Coloring and its Generalizations, New York, USA, Ithaca, Sep. 2002, pp. 112-125. Available from: https://imada.sdu.dk/u/marco/Publications/Files/gcp-ils-Ithaca.pdf

10. A Kosowski and K. Manuszewski, "Classical coloring of graphs," Contemporary Mathematics, vol. 352, pp. 1-20, 2004. Available from: https://umv.science.upjs.sk/madaras/ATG/coloring%20algorithms.pdf

11. Mansuri, V. Gupta, and R. S. Chandel, "Coloring Programs in Graph Theory," Int. Journal of Math. Analysis, vol. 4, no. 50, pp. 2473-2479, Bhopal, (M.P.) India, 2010. Available from: https://www.geeksforgeeks.org/graph-coloring-applications/

12. M. Orouskhani, Y. Orouskhani, M. Mansouri, and M. Teshnehlab, "A Novel Cat Swarm Optimization Algorithm for Unconstrained Optimization Problems," I.J. Information Technology and Computer Science, vol. 11, pp. 32-41, 2013. Available from: https://www.mecs-press.org/ijitcs/ijitcs-v5-n11/IJITCS-V5-N11-4.pdf

13. R. Elio, J. Hoover, I. Nikolaidis, M. Salavatipour, L. Stewart, and K. Wong, "About computing science research methodology," in Google Scholar Google Scholar Reference, 2011. Available from: https://www.semanticscholar.org/paper/About-Computing-Science-Research-Methodology-Elio-Hoover/55a528f0f10b4ff4d4ec40d8fc30460ecf51f697

14. J. R. Allwright, R. Bordawekar, P. D. Coddington, K. Dincer, and C. L. Martin, "A comparison of parallel graph coloring algorithms," SCCS-666, pp. 1-19, 1995. Available from: https://www.researchgate.net/publication/2296563_A_Comparison_of_Parallel_Graph_Coloring_Algorithms

15. W. Matula, G. Marble, and J. D. Isaacson, "Graph coloring algorithms," in Graph Theory and Computing, New York, NY, USA: Academic Press, 1972, pp. 109-122. Available from: https://www.geeksforgeeks.org/graph-coloring-applications/

16. T. Leighton, "A graph coloring algorithm for large scheduling problems," Journal of Research of the National Bureau of Standards, vol. 84, no. 6, p. 489, 1979. Available from: https://nvlpubs.nist.gov/nistpubs/jres/84/jresv84n6p489_a1b.pdf

17. N. Musliu and M. Schwengerer, "Algorithm selection for the graph coloring problem," in International Conference on Learning and Intelligent Optimization, Berlin, Germany, Jan. 2013, pp. 389-403. Available from: https://link.springer.com/chapter/10.1007/978-3-642-44973-4_42

18. "Vertex Coloring: Welsh Powell Algorithm," Module 2: Planning and Scheduling, pp. 53-55. Available from: http://mrsleblancsmath.pbworks.com/w/file/fetch/46119304/vertex%20coloring%20algorithm.pdf

19. M. Taherdangkoo, M. H. Shirzadi, M. Yazdi, and M. HadiBagheri, "A Robust Clustering Method Based on Blind, Naked Mole-Rats (BNMR) Algorithm," Swarm and Evolutionary Computation, vol. 10, pp. 1–11, 2013. Available from: https://www.sciencedirect.com/science/article/abs/pii/S2210650213000035

20. S. C. Chu and P. W. Tsai, "Computational intelligence based on the behavior of cats," International Journal of Innovative Computing, Information and Control, vol. 3, no. 1, pp. 163-173, 2007. Available from: https://www.researchgate.net/publication/228721750_Computational_intelligence_based_on_the_behavior_of_cats

Cites this article as

A. Saeed, A. Husnain, A. Zahoor, R. M. Gondal, "A Comparative Study of Cat Swarm Algorithm for Graph Coloring Problem: Convergence Analysis and Performance Evaluation", International Journal of Innovative Research in Computer Science and Technology (IJIRCST), Vol-12, no.4, pp.1-9, 2024. Available from: https://doi.org/10.55524/ijircst.2024.12.4.1

Corresponding Author

Ayesha Saeed

Research Assistant, Department of Computer Science, University of Chicago, USA

Download Full Paper

Download PDF

No. of Downloads: 7 | No. of Views: 58

Advancing Medical Diagnostics with Deep Learning and Data Preprocessing

Ruilin Xu, Yun Zi, Lu Dai, Haoran Yu, Mengran Zhu.

May 2024 - Vol 12, Issue 3
Securing the Skies- A Critical Analysis of Cloud Infrastructure Vulnerabilities

Vaishnavi Chaudhari, Poonam Dhake, Snehal Salunkhe, Mahendra Suryavanshi.

May 2024 - Vol 12, Issue 3
Integrating Monistic Theory, Neuro-Linguistic Programming, and AI for Developing Emotionally Healthy School Children- A Global and Indian Perspective

Astha Puri, Rohan Mathur.

May 2024 - Vol 12, Issue 3

IJIRCST

A Comparative Study of Cat Swarm Algorithm for Graph Coloring Problem: Convergence Analysis and Performance Evaluation

Citations

Download Full Paper PDF

Total View 58

Total Download 7