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

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

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

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

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

چکیده:

مساله بیدارسازی مجموعه ای از رباتهای خواب توسط یک ربات بیدار اولیه Freeze-Tag Problem (FTP) نام دارد در FTP هدف بیدراسازی کلیه رباتها در کمترین زمان ممکن است این مساله در حالت کلی NP-Hard و درحالت اقلیدسی از جمله مسائل باز OPEN به شمار می رود دراین مقاله الگوریتمهای تقریبی برای fTP درمحیط اقلیدسی مدنظر قرارم یگیرند ابتدا یک الگوریتم تقریبی بافاکتور تقریب O(1 و زمان اجرای O(nlogn که توسط آرکین وهمکارانش ارایه شده است معرفی می گردد و سپس یک الگوریتم با فاکتور تقریب بهتر و زمان اجرای خطی برای مساله ارایه میشود.