Parallel Implementations on the GPU of Algorithms for the Minimum Dominating Set Problem Using Dynamic Programming on Tree Decompositions.

Abstract

Two different algorithms that solve the Minimum Dominating Set problem are implemented in both a sequential, and parallel fashion. The first on the CPU, and the latter using GPU programming. The aim of this work is to find out to what extent these algorithms can be implemented on the GPU, and how these four different implementations compare on different instances. The experimental results show that when the tree width k grows, parallelization of these algorithms provides reductions in run time that can reach multiple orders of magnitude. The sequential implementations do outperform their parallel counterparts for very small bag sizes, due to the overhead associated with the GPU implementations.