بررسی الگوریتم های حل مساله مجموعه غالب وزن دار با محدودیت های مختلف

مجموعه وزنی غالب روی گراف G=(V, E ,w) که در ان w یک تابع است که به هر راس این گراف یک وزن مثبت میدهد .در اینجا مساله پیدا کردن یک زیر مجموعه از راس های این گراف است بطوری که اعضای این مجموعه به دیگر راس های گراف که داخل مجموعه G نیستند مجاور باشد و وزناعضای این مجموعه در مقایسه با دیگر مجموعه ها مینیمم W (V)D ϵv W (D) = Σ باشد. زمانی که W(v)=1 برای همه راس ها، ان گاه مساله مجموعه وزنی غالب به مساله مجموعه غالب تغیر میکند. در نتایج اولیه مساله مجموعه وزنی غالب بر روی گراف های خاص نشان میدهد که این دسته از گراف میتواند در زمان خطی حل شوند.

Keywords:

مجموعه غالب , زمان خطی , مینیمم