Chessboard domination on programmable graphics hardware
Nathan Cournia · 2006
In this paper we present an algorithm to compute the minimum dominating number of a chessboard graph given any chess piece. We use the CPU to compute possible minimally dominating sets, which we then send to programmable graphics hardware to determine the set's domination. We find that the GPU accelerated algorithm performs better than a comparable CPU based algorithm for board sizes greater than 9. To our knowledge, this paper presents the first algorithm to determine the minimum domination number of a chessboard graph using the GPU.