کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
473858 698818 2010 9 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Reactive and dynamic local search for max-clique: Engineering effective building blocks
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر علوم کامپیوتر (عمومی)
پیش نمایش صفحه اول مقاله
Reactive and dynamic local search for max-clique: Engineering effective building blocks
چکیده انگلیسی

This paper presents the results of an ongoing investigation about how different algorithmic building blocks contribute to solving the maximum clique problem. We consider greedy constructions, plateau searches, and more complex schemes based on dynamic penalties and/or prohibitions, in particular the recently proposed technique of dynamic local search and the previously proposed reactive local search (RLS). We design a variation of the original RLS algorithm where the role of long-term memory (LTM) is increased (RLS-LTM). In addition, we consider in detail the effect of the low-level implementation choices on the CPU time per iteration. We present experimental results on randomly generated graphs with different statistical properties, showing the crucial effects of the implementation, the robustness of different techniques, and their empirical scalability.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Computers & Operations Research - Volume 37, Issue 3, March 2010, Pages 534–542
نویسندگان
, ,