کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4958927 | 1445464 | 2017 | 41 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
On minimization of the number of branches in branch-and-bound algorithms for the maximum clique problem
ترجمه فارسی عنوان
برای به حداقل رساندن تعداد شاخه ها در الگوریتم های شعاعی و محدود برای حداکثر مشکل کلید
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
علوم کامپیوتر (عمومی)
چکیده انگلیسی
When searching for a maximum clique in a graph G, branch-and-bound algorithms in the literature usually focus on the minimization of the number of branches generated at each search tree node. We call dynamic strategy this minimization without any constraint, because it induces a dynamic vertex ordering in G during the search. In this paper, we introduce a static strategy that minimizes the number of branches subject to the constraint that a static vertex ordering in G must be kept during the search. We analyze the two strategies and show that they are complementary. From this complementarity, we propose a new algorithm, called MoMC, that combines the strengths of the two strategies into a single algorithm. The reported experimental results show that MoMC is generally better than the algorithms implementing a single strategy.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Computers & Operations Research - Volume 84, August 2017, Pages 1-15
Journal: Computers & Operations Research - Volume 84, August 2017, Pages 1-15
نویسندگان
Chu-Min Li, Hua Jiang, Felip Manyà ,