Implementation of a parallel method for the graph coloring problem using MPI and verification of the number of processors on it

Author

Khayami, Seyyed Raouf ; Alinezhad, A. ; Jafari, Hossein

Author_Institution

Dept. of Comput. Eng. & IT, Univ. of Technol., Shiraz, Iran

fYear

2013

fDate

28-30 May 2013

Firstpage

30

Lastpage

34

Abstract

In this paper, a parallel version based on a pipeline of innovative methods for graph coloring in a sequential mode is presented. The results of the execution time for parallel implementation in the C++ language using the Message Passing Interface (MPI) on a multi-processor machine is presented and discussed. This problem also has been implemented in a fully sequential and recursive mode, in the same environment, and the results of comparing them to parallel implementation have been reported.

Keywords

C++ language; graph colouring; message passing; multiprocessing systems; C++ language; MPI; graph coloring problem; message passing interface; multiprocessor machine; parallel method; processor number verification; recursive mode; sequential mode; Algorithm design and analysis; Arrays; Color; Image color analysis; Message passing; Parallel algorithms; Program processors; graph coloring; message passing interface; parallel algorithm; sequential first fit algorithm;

fLanguage

English

Publisher

ieee

Conference_Titel

Information and Knowledge Technology (IKT), 2013 5th Conference on

Conference_Location

Shiraz

Print_ISBN

978-1-4673-6489-8

Type

conf

DOI

10.1109/IKT.2013.6620033

Filename

6620033