کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
475621 | 699338 | 2014 | 8 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Relaxed approximate coloring in exact maximum clique search
ترجمه فارسی عنوان
رنگ آمیزی تقریبی ملایم در جستجوی حداکثر جستجوی دقیق
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
بهینه سازی ترکیبی، تقریبا رنگ آمیزی، شعبه و مرز، جستجوی جهانی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
علوم کامپیوتر (عمومی)
چکیده انگلیسی
This paper presents selective coloring as a new paradigm for branch-and-bound exact maximum clique search. Approximate coloring has, in recent, years been at the heart of leading solvers in the field. Selective coloring proposes to relax coloring up to a certain threshold. The result is a less informed but lighter decision heuristic.Different operators for the remaining uncolored vertices give rise to algorithmic variants integrated in a new BBMCL framework. BBMCL allows for an interesting comparison between approximate coloring and degree-based decision heuristics.The paper also reports extensive empirical tests. Selective coloring algorithms are fastest for a large subset of the graphs considered.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Computers & Operations Research - Volume 44, April 2014, Pages 185–192
Journal: Computers & Operations Research - Volume 44, April 2014, Pages 185–192
نویسندگان
Pablo San Segundo, Cristobal Tapia,