برای اطلاع از آخرین مقالات علمی و اخبار کرونا(COVID-19) کلیک کنید

مشخصات مقاله

عنوان: 

يك الگوريتم تقريبي جديد براي پوشش چندضلعي هاي ساده با نواحي ستاره اي

نوع ارائه: مقاله
نویسنده: حسين زاده مقدم محمد,باقري عليرضا
 
 
 
عنوان همایش: كنفرانس ملي سالانه انجمن كامپيوتر ايران
نوع همایش:  انجمن هاي علمي
حامی:  انجمن کامپیوتر ایران، دانشگاه صنعتی شریف
زمان:  1386دوره 13
 
 
چکیده: 

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

 
کلید واژه: الگوريتم تقريبي، پوشش چندضلعي ها، مساله گالري هنري، نگهباني نقطه اي، نواحي ستاره اي
 
مقالات نشریه ای مرتبط: 
 
مقالات همایشی مرتبط: 
 
 
بازدید یکساله 77   pdf-file
 
آخرین های بلاگ
ورود به بلاگ مرکز اطلاعات علمی