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

مجموعه پوشش راسی برای یک گراف، زیر مجموعه ای از راس های گراف است به طوری که حداقل یکی از راس های هر یال گراف عضو آن مجموعه باشد. مسئله پوشش راسی، پیدا کردن پوشش راسی با اندازه مینیمم است. مسئله پوشش راسی یکی از مسائل بهینه سازی ترکیبیاتی کلاسیک در حوزه گراف است که کاربردهای زیادی در زندگی و علوم مانند مانیتورینگ و امنیت شبکه دارد. این ایده اولین بار توسط کوک مطرح شد و سپس او ثابت کرد که مسئله پوشش راسی NP- سخت است. کارپ نیز نشان داد که مسئله تصمیم گیری پوشش راسی N-NP کامل است. علاوه بر این تقریب مسئله پوشش راسی برای هر ضریب تقریب کمتر از ۱.۳۶.۶ یک مسئله NP- کامل است. در این مقاله این مسئله را معرفی و یک الگوریتم جدید به نام MVSD که پیچیدگی زمانی آن ᶞ nc/ ارائه نموده ایم که در آن n تعداد راس های گراف ، C اندازه پوشش راسی و ᶞ مینیمم درجه گراف است

کلیدواژه ها:

پوشش راسی ، الگوریتم های جستجوی محلی ، الگوریتم های حریصانه ، مسائل NP-سخت