This representation is optimal for this kind of problem since all coloring algorithms require that, given a vertex, a list of the vertex's neighbours is known. To represent the graph internally, we decided to adopt the adjacency list representation. Dinçer, Christine Martin, “A Comparison of Parallel Graph Coloring Algorithms” (1995), in order to have a more technical understanding of how sequential and parallel graph coloring algorithms can be implemented, and compare the results obtained by us with the results obtained in the article. The problem of Graph Coloring consists in assigning labels (usually referred to as "colors") to each vertex of a graph, such that two adjacent vertices do not have the same color.Īfter looking up for some general information about the topic, we based most of our work on an article by J.
The first step involved learning what the problem of Graph Coloring is, and how the various coloring algorithms work. This document points out all the resources used, the design choices adopted and experimental evaluations obtained during the development of the project. Average coloring times by number of threads.Average coloring times and colors used by coloring method (RGGs only).Average colors used by coloring method (without outliers).Average colors used by coloring method (all graphs).
0 kommentar(er)
