Title: Can the hybrid colouring algorithm take advantage of multi-core architectures?

Authors: João Fabrício Filho; Luis Gustavo Araujo Rodriguez; Anderson Faustino Da Silva

Addresses: Federal University of Technology – Paraná, Via Rosalina Maria dos Santos, 1233, Campo Mourão/PR, Brazil ' Department of Informatics, State University of Maringá, Colombo Avenue, 5790, Block C56, Maringá/PR, Brazil ' Department of Informatics, State University of Maringá, Colombo Avenue, 5790, Block C56, Maringá/PR, Brazil

Abstract: Graph colouring is a complex computational problem that focuses on colouring all vertices of a given graph using a minimum number of colours. However, adjacent vertices are restricted from receiving the same colour. Over recent decades, various algorithms have been proposed and implemented to solve such a problem. An interesting algorithm is the hybrid colouring algorithm, which was developed in 1999 by Galinier and Hao. The hybrid colouring algorithm was widely regarded at the time as one of the best performing algorithms for graph colouring. Nowadays, high-performance out-of-order multi-cores have emerged; consequently, executing applications faster and efficiently. Thus, the objective of this paper is to analyse whether the hybrid colouring algorithm can take advantage of multi-core architectures, in terms of performance, or not. For this purpose, we propose and implement a parallel version of the hybrid colouring algorithm that takes advantage of all hardware resources. Several experiments were performed on a machine with two Intel(R) Xeon(R) CPU E5-2630 processors, thus having a total of 24 cores. The experiment proved that the parallel hybrid colouring algorithm, using multi-core architectures, is a significant improvement over the original because it achieves enhancements of up to 40% in terms of the distance to the best chromatic number found in the literature. The expected contribution of this paper is to encourage developers to take advantage of high performance out-of-order multi-cores to solve complex computational problems.

Keywords: metaheuristics; hybrid colouring algorithm; HCA; graph; graph colouring problem; GCP; modern computer architecture.

DOI: 10.1504/IJCSE.2019.104434

International Journal of Computational Science and Engineering, 2019 Vol.20 No.4, pp.457 - 479

Received: 15 Mar 2017
Accepted: 31 Jul 2017
Published online: 12 Jan 2020 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article