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

چکیده مقاله

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

کلیدواژه‌ها

نویسندگان

احمد شکرانی بایگی

استادیار دانشکده کامپیوتر و فناوری اطلاعات، دانشگاه سجاد، مشهد

�کرانی بایگی، احمد،1404،مسئله پوشش راسی با گنجایش سخت بر روی ابرگراف ها،بیست و هشتمین کنفرانس ملی علوم و مهندسی کامپیوتر و فناوری اطلاعات،بابل

ارائه‌شده در

مجموعه مقالات بیست و هشتمین کنفرانس ملی علوم و مهندسی کامپیوتر و فناوری اطلاعات29 آبان 1404 · بابل