Parallelization of BitColor Algorithm via Multithreading and GPU for Graph Coloring

Abstract

The graph coloring problem, a fundamental NP-hard challenge, has numerous applications in scheduling, register allocation, and network optimization. Traditional sequential algorithms for graph coloring are computationally expensive, particularly for large-scale graphs. In this paper, we propose the Parallel BitColor Algorithm (PBitCo), an extension of the BitColor framework, designed to exploit the parallel processing capabilities of modern CPU and GPU architectures. The PBitCo algorithm utilizes bitwise operations to reduce computation time and employs parallel execution on widely accessible platforms to further enhance performance. We implemented and tested the algorithm on various graph instances, comparing its performance against conventional graph coloring methods. Our results demonstrate that PBitCo achieves significant speedups, with the GPU implementation delivering up to a 10x improvement over baseline methods. © 2025 Elsevier B.V., All rights reserved.