مشاهده مشخصات مقاله
پیچیدگی زمانی تولید زنجیره‌های ساده مجزا از دو مجموعه نقطه مجزا در فضای دوبعدی
|
Authors |
-
عبداله سپه‌وند
-
محمدرضا رزازی
|
|
Conference |
بیست و سومین کنفرانس ملی سالانه انجمن کامپیوتر ایران |
|
Abstract |
پیدا کردن دو مسیر ساده از دو مجموعه نقطه مجزا اولین بار توسط جف اریکسون مطرح شد. این مسئله می‌تواند در مسیریابی حرکت ربات‌ها، تولید چندضلعی‌های تصادفی، طراحی مدارهای VLSI و غیره کاربرد داشته باشد. در این مقاله اثبات می‌کنیم که حالت عمومی این مسئله یعنی رسم r زنجیره قرمز ساده و b زنجیره آبی ساده از دو مجموعه نقطه مجزای داده‌شده به‌طوری‌که تمام نقاط را پوشش دهند ان پی‌کامل است. برای اثبات ان پی-کامل بودن، از مسئله «پیدا کردن مسیر همیلتونی در گراف‌های مسطح که با یال‌های خط مستقیم رسم شده‌اند» که خود یک مسئله ان پی-کامل است استفاده می‌کنیم و آن را به مسئله مطرح‌شده کاهش می‌دهیم. |
|
قیمت |
-
برای اعضای سایت : 100,000 Rial
-
برای دانشجویان عضو انجمن : 20,000 Rial
-
برای اعضای عادی انجمن : 40,000 Rial
|
خرید مقاله
|
|
.gif){kind=icon}