روش مبتنی بر جستجوی هسته برای حل مساله شناسایی رئوس مهم گراف

مساله شناسایی رئوس مهم در گراف یکی از مسائل بهینه سازی شناخته شده است که در تحلیل شبکه های اجتماعی، حمل ونقل، زیستی و غیره کاربردهای فراوانی دارد. اما این م ساله -NP سخت ا ست و ارائه یک روش ابتکاری کارآمد برای حل آن ضرورت دارد. از سوی دیگر روش ابتکاری جستجوی هسته یک روش ابتکاری جدید است که اخیرا0 برای حل مسائل MIP مطرح شده است. در این مقاله به ارائه صورت بهبودیافته ای از این روش برای حل مساله شناسایی رئوس مهم در گراف میپردازیم که در آن در تشکیل هسته از شاخص مرکزیت بینابینی ا ستفاده میگردد. نتایج محا سباتی نشان میدهند که الگوریتم پیشنهادی برای گرافهای متو سط و نسبتا بزرگ با بیش از500 یال عملکرد بسیار بهتری نسبت به بهینه یاب CPLEX (در محدودیت زمانی 3600 ثانیه) از نظر کیفیت جواب و زمان حل دارد.

کلیدواژه ها:

شناسایی رئوس مهم گراف ، روش جستجوی هسته ، روش تطبیقی جستجوی هسته ، شاخص مرکزیت بینابینی