A parallel search tree algorithm for vertex cover on graphical processing units. (c2013)

LAUR Repository

Show simple item record

dc.contributor.author Kabbara, Rashad Karim
dc.date.accessioned 2013-11-18T12:30:49Z
dc.date.available 2013-11-18T12:30:49Z
dc.date.issued 2013-11-18
dc.date.submitted 2013-02-01
dc.identifier.uri http://hdl.handle.net/10725/1637
dc.description Includes bibliographical references (p. 29-30). en_US
dc.description.abstract 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. en_US
dc.language.iso en en_US
dc.subject Computer algorithms en_US
dc.subject Graphics processing units -- Programming en_US
dc.subject Trees (Graph theory) -- Data processing en_US
dc.subject Lebanese American University -- Dissertations en_US
dc.subject Dissertations, Academic en_US
dc.title A parallel search tree algorithm for vertex cover on graphical processing units. (c2013) en_US
dc.type Thesis en_US
dc.term.submitted Fall en_US
dc.author.degree MS in Computer Science en_US
dc.author.school Arts and Sciences en_US
dc.author.idnumber 200803588 en_US
dc.author.commembers Dr. Haidar Harmanani
dc.author.commembers Dr. Ramzi Haraty
dc.author.woa OA en_US
dc.description.physdesc 1 bound copy: xii, 30 leaves; ILL.; 30 cm. available at RNL. en_US
dc.author.division Computer Science en_US
dc.author.advisor Dr. Faisal Abu-Khzam
dc.keywords Parallel programming en_US
dc.keywords Exact algorithms en_US
dc.keywords Graph problems en_US
dc.keywords Graphical processing units en_US
dc.keywords Vertex cover en_US
dc.identifier.doi https://doi.org/10.26756/th.2013.26 en_US
dc.publisher.institution Lebanese American University en_US

Files in this item

This item appears in the following Collection(s)

Show simple item record

Search LAUR

Advanced Search


My Account