However by assigning weights to each vertex based on certain constraints, parallelisation can be made possible. The serial implementation for the algorithm is an iterative greedy algorithm that is strictly sequential making parallelisation considerably difficult. This way 1-dimensional arrays can be used, thereby benefitting paralleliation.
Adjacency List Pointer array- To store the pointer to the first element of the adjacency list of each vertex.Įx: Adjacency list of vertex v starts at adjList] and ends at adjList]-1.Adjacency List array - To store the adjacency list of each vertex.The Compressed Sparse Row (CSR) format has been used to represent the graphs and work with them in parallel. The goal of this project is to obtain a balanced coloring of the graph i.e, the number of colors used is made as close as possible to the chromatic number (minimum number for that graph) to ensure some degree of load balancing. c(i) is referred to as the color of vertex i.įinding the optimal graph coloring is an NP-Complete problem. A coloring of a graph G is a mapping c : V -> such that c(i) != c(j) for all edges (i, j) belonging to E.
The edges are of the form (i, j) where i,j belong to V. The problem statement is as follows:Īn undirected graph G is a set of vertices V and a set of edges E. We deal with a special case of graph coloring called " Vertex Coloring". In general, graph coloring can refer to conditionally labelling any component of a graph such as its vertices or edges. Parallel Graph Coloring with Cuda C++ Introduction
0 kommentar(er)
