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

Faisal Abu-Khzam, Rashad Karim Kabbara

مدرسة الآداب والعلوم-الجامعة اللبنانية الأميركية · لبنان

الموضوعات

علوم تطبيقية وتكنولوجية

الملخص

Graphical Processing Units (GPUs) have become popular recently due their highly parallelshared-memory architectures. The computational challenge posed by NP-Hard problems makes them potential targets to GPU-based computations, especially when solved by exactexponential-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.

روابط وملفات

الوثيقة في المستودع الخارجي عرض في AskZad

التعريف والنوع

رقم الوثيقة: fbaec2b8-790e-474a-893a-166b13a1e9af
رقم العقد: 0
نوع الوسائط: Crawler
نوع المحتوى: الرسائل العلمية
صيغة المصدر: رسائل ماجيستير
نوع الملف: pdf text
أسماء الملفات: 2213233_1.pdf

بيانات النشر

ألقاب المؤلفين: [{"name_ar":" Faisal Abu-Khzam","title_ar":"اشراف","title_en":"Supervision"},{"name_ar":" Rashad Karim Kabbara","title_ar":"اعداد","title_en":"Preparation"}]
اللغة: English

المصدر والدورية

اسم المصدر: A parallel search tree algorithm for vertex cover on graphical processing units

المحتوى والصفحات

عدد الصفحات: 0
كلمات الباحثين: graphical processing

إشراف وإعداد

الإشراف: Faisal Abu-Khzam
الإعداد: Rashad Karim Kabbara

الاقتباسات الببليوغرافية

APA

Faisal Abu-Khzam و Rashad Karim Kabbara. (2013). A parallel search tree algorithm for vertex cover on graphical processing units. أطروحة(رسائل ماجيستير). مدرسة الآداب والعلوم-الجامعة اللبنانية الأميركية. لبنان.

MLA

Faisal Abu-Khzam و Rashad Karim Kabbara. A parallel search tree algorithm for vertex cover on graphical processing units. 2013. مدرسة الآداب والعلوم-الجامعة اللبنانية الأميركية، رسائل ماجيستير.