الگوریتم تقریبی برای مسئله حداقل پوشش راسی با رویکرد استراتژیک مبتنی بر توزیع درجات
محل انتشار: پنجمین کنفرانس بین المللی محاسبات نرم
سال انتشار: 1402
نوع سند: مقاله کنفرانسی
زبان: فارسی
مشاهده: 60
متن کامل این مقاله منتشر نشده است و فقط به صورت چکیده یا چکیده مبسوط در پایگاه موجود می باشد.
توضیح: معمولا کلیه مقالاتی که کمتر از ۵ صفحه باشند در پایگاه سیویلیکا اصل مقاله (فول تکست) محسوب نمی شوند و فقط کاربران عضو بدون کسر اعتبار می توانند فایل آنها را دریافت نمایند.
- صدور گواهی نمایه سازی
- من نویسنده این مقاله هستم
استخراج به نرم افزارهای پژوهشی:
شناسه ملی سند علمی:
CSCG05_146
تاریخ نمایه سازی: 9 اردیبهشت 1403
چکیده مقاله:
در این مقاله ، مسئله کمترین پوشش راسی یا Minimum Vertex Cover به عنوان یک مسئله کلاسیک بهینه سازی گراف با پیچیدگی NP-complete مورد بررسی قرار گرفته است . ما یک الگوریتم موثر با نامStrategic Approach Based On Degree Distribution in Minimum Vertex Cover Problem (SABOD) طراحی کردهایم تا کمترین پوشش گرههای یک گراف را بدست آوریم . عملکرد SABOD برروی تعداد زیادی از گرافهای تصادفی و گرافهای بنچمارک DIMACS, BHOSLIB و گرافهای واقعی مانند شبکه اجتماعی مورد آزمایش قرار گرفته و با سایر روشهای موجود مقایسه شده است . نتایج گستردهی شبیه سازی نشان می دهد که SABOD ممکن است راهحل های بهتری نسبت به الگوریتم های موجود برای حل مسئله کمترین پوشش گره ارائه دهد.
کلیدواژه ها:
نویسندگان
معین منعمی
دانشجوی کارشناسی ارشد الگوریتم و محاسبات ، دانشکدگان فنی دانشگاه تهران
فاطمه ولی پور
دانشجوی کارشناسی ارشد الگوریتم و محاسبات، دانشکدگان فنی دانشگاه تهران
روح اله عابدیان
استادیار دانشکده ی علوم مهندسی دانشگدگان فنی دانشگاه تهران