Title :
An algorithm to solve the Dominating Set Problem on GPUs
Author :
Trefftz, Christian
Author_Institution :
Sch. of Comput., Grand Valley State Univ., Allendale, MI, USA
Abstract :
A brute-force algorithm to solve small instances of the Dominating Set Problem on GPUs is presented. Two implementations of the algorithm are discussed, one that uses atomic operations and one that uses reductions. Experimental results are reported.
Keywords :
graphics processing units; set theory; GPU; atomic operations; brute force algorithm; dominating set problem; Arrays; Encoding; Graphics processing unit; Instruction sets; Kernel; Memory management;
Conference_Titel :
Electro/Information Technology (EIT), 2012 IEEE International Conference on
Conference_Location :
Indianapolis, IN
Print_ISBN :
978-1-4673-0819-9
DOI :
10.1109/EIT.2012.6220697
