بررسی الگوریتم های حل مساله مجموعه غالب وزن دار با محدودیت های مختلف
سال انتشار: 1396
نوع سند: مقاله کنفرانسی
زبان: فارسی
مشاهده: 493
فایل این مقاله در 9 صفحه با فرمت PDF قابل دریافت می باشد
- صدور گواهی نمایه سازی
- من نویسنده این مقاله هستم
استخراج به نرم افزارهای پژوهشی:
شناسه ملی سند علمی:
ITCT04_114
تاریخ نمایه سازی: 17 آبان 1396
چکیده مقاله:
مجموعه وزنی غالب روی گراف G=(V, E ,w) که در ان w یک تابع است که به هر راس این گراف یک وزن مثبت میدهد .در اینجا مساله پیدا کردن یک زیر مجموعه از راس های این گراف است بطوری که اعضای این مجموعه به دیگر راس های گراف که داخل مجموعه G نیستند مجاور باشد و وزناعضای این مجموعه در مقایسه با دیگر مجموعه ها مینیمم W (V)D ϵv W (D) = Σ باشد. زمانی که W(v)=1 برای همه راس ها، ان گاه مساله مجموعه وزنی غالب به مساله مجموعه غالب تغیر میکند. در نتایج اولیه مساله مجموعه وزنی غالب بر روی گراف های خاص نشان میدهد که این دسته از گراف میتواند در زمان خطی حل شوند.
کلیدواژه ها:
نویسندگان
رامین امیری
دانشجو ارشد دانشگاه شهید بهشتی
حمید شجاع ناظری
دانشجو دکترا دانشگاه فدریشن استرالیا