On comparing algorithms for the maximum clique problem

چندین الگوریتم برای حل دقیق مسأله حداکثر کلاسی در ادبیات موجود است. بعضی از آنها با هدف محدود کردن پیچیدگی بدترین مشکل در نظر گرفته شده اند، در حالی که دیگران به صورت تجربی ارزیابی عملکرد تمرکز می کنند. این دو گروه از آثار تا حدودی مستقل هستند، به این معنی که تحقیقات کمی در مورد گروه آزمایشی در دسترس است و تحلیل کمی نظری در مورد آن وجود دارد. علاوه بر این، نتایج تجربی به نظر می رسد بسیار بهتر از آنچه می تواند از نتایج نظری انتظار می رود. ما نشان می دهیم که یک کلاس گسترده از الگوریتم های شاخه و کران برای حداکثر مشکل کلید نشان می دهد که نمایش زمان متوسط ​​زمان نمایش زمان متوسط ​​نمایش داده شده است و همچنین نشان می دهد که چگونه این توضیح می دهد که اختلاف ظاهری بین نتایج نظری و تجربی است. ما همچنین یک روش ساخت یافته تر برای تجزیه و تحلیل تجربی الگوریتم های برای حداکثر مشکل کلید ارائه می دهیم، که با توجه به ویژگی های کلاه ها در نمودارهای تصادفی، روش های نظری و تجربی را در جستجوی الگوریتم های بهتر نزدیک می کند. به عنوان یک اثبات مفهوم، ما روش پیشنهادی را به سیزده الگوریتم از ادبیات اعمال می کنیم.