الگوریتم تقریبی جدید برای پوشش چندضلعیهای ساده با نواحی ستارهای
Publish place: 13th Annual Conference of Computer Society of Iran
Publish Year: 1386
نوع سند: مقاله کنفرانسی
زبان: Persian
View: 1,769
This Paper With 6 Page And PDF Format Ready To Download
- Certificate
- من نویسنده این مقاله هستم
استخراج به نرم افزارهای پژوهشی:
شناسه ملی سند علمی:
ACCSI13_120
تاریخ نمایه سازی: 25 آبان 1386
Abstract:
چکیده : مسئله پوشش چندضلعی های ساده با کمترین تعداد نواحی ستارهای NP-hard است . بنابراین طراحی الگوریتم های تقریبی در این زمینه از اهمیت بسیاری برخوردار است . تا به حال برای این مسئله الگوریتم تقریبی که فاکتور تقریبش بهتر از n/ 3 باشد طراحی نشده است . ما در این مقاله الگوریتم تقریبی جدیدی با فاکتور تقریب [n / 8] برای مسئله مذکور ارائه کرده ایم که دارای زمان اجرای O(n )3 میباشد .
Keywords:
Authors
محمد حسین زاده مقدم
دانشگاه آزاد اسلامی هشترود، گروه کامپیوتر هشترود، ایران
علیرضا باقری
دانشکده مهندسی کامپیوتر و فناوری اطلاعات، دانشگاه صنعتی امیرکبیر، ت