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

Publish Year: 1400
نوع سند: مقاله کنفرانسی
زبان: Persian
View: 837

This Paper With 5 Page And PDF and WORD Format Ready To Download

  • Certificate
  • من نویسنده این مقاله هستم

استخراج به نرم افزارهای پژوهشی:

لینک ثابت به این Paper:

شناسه ملی سند علمی:

TECCONF05_107

تاریخ نمایه سازی: 11 مهر 1400

Abstract:

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

Keywords:

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

Authors

رامین امیری

دانشکده علوم کامپیوتر، دانشگاه تبریز تبریز، ایران

زهرا بنی اسد

دانشکده ریاضی و کامپیوتر،دانشگاه شهید باهنر کرمان، ایران