یک الگوریتم تقریبی با فاکتور تقریب ثابت و زمان اجرای خطی برای مساله ی freez_tag اقلیدسی
Publish place: 16th annual CSI Computer Conference
Publish Year: 1389
نوع سند: مقاله کنفرانسی
زبان: Persian
View: 924
This Paper With 5 Page And PDF Format Ready To Download
- Certificate
- من نویسنده این مقاله هستم
استخراج به نرم افزارهای پژوهشی:
شناسه ملی سند علمی:
CSICC16_130
تاریخ نمایه سازی: 28 بهمن 1390
Abstract:
مساله بیدارسازی مجموعه ای از رباتهای خواب توسط یک ربات بیدار اولیه Freeze-Tag Problem (FTP) نام دارد در FTP هدف بیدراسازی کلیه رباتها در کمترین زمان ممکن است این مساله در حالت کلی NP-Hard و درحالت اقلیدسی از جمله مسائل باز OPEN به شمار می رود دراین مقاله الگوریتمهای تقریبی برای fTP درمحیط اقلیدسی مدنظر قرارم یگیرند ابتدا یک الگوریتم تقریبی بافاکتور تقریب O(1 و زمان اجرای O(nlogn که توسط آرکین وهمکارانش ارایه شده است معرفی می گردد و سپس یک الگوریتم با فاکتور تقریب بهتر و زمان اجرای خطی برای مساله ارایه میشود.
Keywords:
Authors
زهرا معز کریمی
دانشجوی کارشناسی ارشد ،دانشکده مهندسی کامپیوتر و فناوری اطلاعات،دان
علیرضا باقری
استادیار،دانشکده مهندسی کامپیوتر و فناوری اطلاعات،دانشگاه صنعتی ام
احسان یزدی
دانشجوی کارشناسی ارشد ،دانشکده مهندسی کامپیوتر و فناوری اطلاعات،دان
مراجع و منابع این Paper:
لیست زیر مراجع و منابع استفاده شده در این Paper را نمایش می دهد. این مراجع به صورت کاملا ماشینی و بر اساس هوش مصنوعی استخراج شده اند و لذا ممکن است دارای اشکالاتی باشند که به مرور زمان دقت استخراج این محتوا افزایش می یابد. مراجعی که مقالات مربوط به آنها در سیویلیکا نمایه شده و پیدا شده اند، به خود Paper لینک شده اند :