10947

A parallel search tree algorithm for vertex cover on graphical processing units

Rashad Karim Kabbara
Lebanese American University
Lebanese American University, 2013

@article{kabbara2013parallel,

   title={A parallel search tree algorithm for vertex cover on graphical processing units.(c2013)},

   author={Kabbara, Rashad Karim},

   year={2013}

}

Download Download (PDF)   View View   Source Source   

989

views

Graphical Processing Units (GPUs) have become popular recently due their highly parallel shared-memory architectures. The computational challenge posed by NP-Hard problems makes them potential targets to GPU-based computations, especially when solved by exact exponential-time algorithms. Using the classical NP-hard Vertex Cover problem as a case study, we provide a framework for GPU-based solutions by exploiting the highly parallel structure of the GPU to accelerate the expansion of search-states in commonly used recursive backtracking algorithms. Experimental results show that our method can achieve huge speedups on randomly generated sparse graphs, as well as hard instances from the DIMACS benchmark.
Rating: 2.3. From 2 votes.
Please wait...

* * *

* * *

HGPU group © 2010-2017 hgpu.org

All rights belong to the respective authors

Contact us: