An island-parallel ensemble metaheuristic algorithm for large graph coloring problems

Date

2025-04-01

Author

Coşar, Ahmet

Metadata

Show full item record

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Item Usage Stats

57
views

34
downloads

Cite This

Graph Coloring Problem (GCP) is an NP-Hard vertex labeling problem in graphs such that no two adjacent vertices can have the same color. Large instances of GCP cannot be solved in reasonable execution times by exact algorithms. Therefore, soft computing approaches, such as metaheuristics, have proven to be very efficient for solving large instances of GCP. In this study, we propose a new island-parallel ensemble metaheuristic algorithm (PEM-Color) to solve large GCP instances. Ensemble learning is a new machine learning approach based on combining the output of multiple models instead of using a single one. We use Message Passing Interface (MPI) parallel computation libraries to combine recent state-of-the-art metaheuristics: Harris Hawk Optimization (HHO), Artificial Bee Colony (ABC), and Teaching Learning Based (TLBO) to improve the quality of their solutions further. To the best of our knowledge, this is the first study that combines metaheuristics and applies to the GCP using an ensemble approach. We conducted experiments on large graph instances from the well-known DIMACS benchmark using 64 processors and achieved significant improvements in execu tion times. The experiments also indicate an almost linear speed-up with a strong scalability potential. The solution quality of the instances is promising, as our algorithm outperforms 13 state-of-the-art algorithms

Subject Keywords

Graph coloring, Ensemble, Optimization, TabuCol, Parallelization

URI

https://arxiv.org/pdf/2504.15082
https://hdl.handle.net/11511/117436

Collections

Department of Computer Engineering, Article