مسئله پوشش راسی با گنجایش سخت بر روی ابرگراف ها

بسیاری از مسائل بهینه سازی در علوم کامپیوتر در حوزه ان پی-سخت می باشند لذا بهدست آوردن جواب های بهینه برای آنها در زمان چندجملهای دور از دسترس می باشد. در این مقاله به بررسی پیدا کردن پوشش راسی با استفاده از الگوریتمهای تقریبی برای ابرگرافهایی که رئوس آنها یک گنجایش محدود دارند پرداخته می شود. برای رسیدن به این هدف، دو الگوریتم تقریبی بیان و مقایسه می گردد. در الگوریتم اول یک روش آزمند و با به کارگیری روش مکاشفه ای این مسئله حل میشود. در الگوریتم دوم جواب های حاصل از حل برنامه ریزی خطی همراه با عمل آرام سازی آن و انجام گرد کردن برای رسیدن به جواب بهینه با تقریب f بیان می گردد.

کلیدواژه ها:

ابرگراف ها ، برنامه ریزی خطی ، پوشش راسی