ارائه یک الگوریتم جدید برای حل مسئله پوشش راسی در گراف
- سال انتشار: 1400
- محل انتشار: پنجمین کنفرانس ملی فناوری در مهندسی برق و کامپیوتر (Tec ۲۰۲۱)
- کد COI اختصاصی: TECCONF05_107
- زبان مقاله: فارسی
- تعداد مشاهده: 1072
نویسندگان
دانشکده علوم کامپیوتر، دانشگاه تبریز تبریز، ایران
دانشکده ریاضی و کامپیوتر،دانشگاه شهید باهنر کرمان، ایران
چکیده
مجموعه پوشش راسی برای یک گراف، زیر مجموعه ای از راس های گراف است به طوری که حداقل یکی از راس های هر یال گراف عضو آن مجموعه باشد. مسئله پوشش راسی، پیدا کردن پوشش راسی با اندازه مینیمم است. مسئله پوشش راسی یکی از مسائل بهینه سازی ترکیبیاتی کلاسیک در حوزه گراف است که کاربردهای زیادی در زندگی و علوم مانند مانیتورینگ و امنیت شبکه دارد. این ایده اولین بار توسط کوک مطرح شد و سپس او ثابت کرد که مسئله پوشش راسی NP- سخت است. کارپ نیز نشان داد که مسئله تصمیم گیری پوشش راسی N-NP کامل است. علاوه بر این تقریب مسئله پوشش راسی برای هر ضریب تقریب کمتر از ۱.۳۶.۶ یک مسئله NP- کامل است. در این مقاله این مسئله را معرفی و یک الگوریتم جدید به نام MVSD که پیچیدگی زمانی آن ᶞ nc/ ارائه نموده ایم که در آن n تعداد راس های گراف ، C اندازه پوشش راسی و ᶞ مینیمم درجه گراف استکلیدواژه ها
پوشش راسی، الگوریتم های جستجوی محلی، الگوریتم های حریصانه، مسائل NP-سختمقالات مرتبط جدید
اطلاعات بیشتر در مورد COI
COI مخفف عبارت CIVILICA Object Identifier به معنی شناسه سیویلیکا برای اسناد است. COI کدی است که مطابق محل انتشار، به مقالات کنفرانسها و ژورنالهای داخل کشور به هنگام نمایه سازی بر روی پایگاه استنادی سیویلیکا اختصاص می یابد.
کد COI به مفهوم کد ملی اسناد نمایه شده در سیویلیکا است و کدی یکتا و ثابت است و به همین دلیل همواره قابلیت استناد و پیگیری دارد.