Can the hybrid colouring algorithm take advantage of multi-core architectures?
by João Fabrício Filho; Luis Gustavo Araujo Rodriguez; Anderson Faustino Da Silva
International Journal of Computational Science and Engineering (IJCSE), Vol. 20, No. 4, 2019

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.

Online publication date: Sun, 12-Jan-2020

The full text of this article is only available to individual subscribers or to users at subscribing institutions.

 
Existing subscribers:
Go to Inderscience Online Journals to access the Full Text of this article.

Pay per view:
If you are not a subscriber and you just want to read the full contents of this article, buy online access here.

Complimentary Subscribers, Editors or Members of the Editorial Board of the International Journal of Computational Science and Engineering (IJCSE):
Login with your Inderscience username and password:

Username:        Password:          Forgotten your password?

Want to subscribe?
A subscription gives you complete access to all articles in the current issue, as well as to all articles in the previous three years (where applicable). See our Orders page to subscribe.

If you still need assistance, please email subs@inderscience.com