سال انتشار: ۱۳۸۶

محل انتشار: سیزدهمین کنفرانس سالانه انجمن کامپیوتر ایران

تعداد صفحات: ۶

نویسنده(ها):

محمد حسین زاده مقدم – دانشگاه آزاد اسلامی هشترود، گروه کامپیوتر هشترود، ایران
علیرضا باقری – دانشکده مهندسی کامپیوتر و فناوری اطلاعات، دانشگاه صنعتی امیرکبیر، ت

چکیده:

چکیده : مسئله پوشش چندضلعی های ساده با کمترین تعداد نواحی ستارهای NP-hard است . بنابراین طراحی الگوریتم های تقریبی در این زمینه از اهمیت بسیاری برخوردار است . تا به حال برای این مسئله الگوریتم تقریبی که فاکتور تقریبش بهتر از n/ 3 باشد طراحی نشده است . ما در این مقاله الگوریتم تقریبی جدیدی با فاکتور تقریب [n / 8]برای مسئله مذکور ارائه کرده ایم که دارای زمان اجرای O(n )3 میباشد .