Parallel Discrete Harmony Search Algorithm for the Graph Coloring Problem

Graph coloring is an NP-hard combinatorial optimization problem with significant implications in both theoretical and practical contexts due to its complexity and extensive applicability. In this work, a novel approach is proposed to address the graph coloring problem through a parallel discrete Har...

Full description

Saved in:
Bibliographic Details
Published in:Engineering, technology & applied science research technology & applied science research, 2024-10, Vol.14 (5), p.17317-17323
Main Authors: Chemaa, Sofiane, Kout, Akram, Djelloul, Halima, Harrag, Nassir
Format: Article
Language:English
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Graph coloring is an NP-hard combinatorial optimization problem with significant implications in both theoretical and practical contexts due to its complexity and extensive applicability. In this work, a novel approach is proposed to address the graph coloring problem through a parallel discrete Harmony Search algorithm, termed PDHSCol. By harnessing the robustness of the Harmony Search algorithm and integrating parallel processing, our algorithm enhances performance by concurrently generating and evaluating multiple solutions. Implemented in MATLAB, PDHSCol was evaluated using a variety of DIMACS benchmark instances. The experimental results demonstrate that the algorithm performs effectively and yields promising improvements over various other methods, highlighting its potential to deliver high-quality solutions.
ISSN:2241-4487
1792-8036
DOI:10.48084/etasr.8565