Evaluation of Serial and Parallel Shared-Memory Distance-1 Graph Coloring Algorithms

Within the scope of computational science and engineering, the standard graph coloring problem, the distance-1 coloring, is typically used to select independent sets on which subsequent parallel computations can be guaranteed. As graph coloring is an active field of research, various algorithms are available, each offering advantages and disadvantages. We compare several serial as well as parallel shared-memory graph coloring algorithms for the standard graph coloring problem based on reference graphs. Our investigation covers well established as well as recent algorithms and their support for balanced and unbalanced approaches. An overview on speedup, used number of colors, and their respective population for different test graphs is provided. It is shown that the parallel approaches produce similar results as the serial methods, but for specific cases the serial algorithms still remain a good option, when certain properties (e.g., balancing) are of major importance.