کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4958872 | 1445458 | 2018 | 33 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
A CPU-GPU local search heuristic for the maximum weight clique problem on massive graphs
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
علوم کامپیوتر (عمومی)
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
Given an undirected graph with positive weights on the vertices, the Maximum Weight Clique Problem (MWCP) consists in finding a clique with maximum total weight. In this paper, we present a CPU-GPU local search heuristic for solving the MWCP on massive graphs. The heuristic is based on two new neighborhood structures for the problem. These neighborhoods are explored using an efficient procedure that is suitable to be mapped onto a GPU-based massively parallel architecture. We test the proposed heuristic on real-world massive graphs with millions of edges and vertices. The results indicate that, even when the heuristic is executed on a CPU-only architecture, it is able to outperform the best-known heuristics for the MWCP. Moreover, the hybrid CPU-GPU implementation obtained an average speedup of up to 12 times over the CPU-only implementation.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Computers & Operations Research - Volume 90, February 2018, Pages 232-248
Journal: Computers & Operations Research - Volume 90, February 2018, Pages 232-248
نویسندگان
Bruno Nogueira, Rian G.S. Pinheiro,