علی نوراله - آزمایشگاه تحقیق وتوسعه نرم افزار دانشکده مهندسی کامپیوتر و فناوری ا
محمدرضا رزازی

یکی از مسائل معروف درهندسه محاسباتی مسئله تا کردن خط کش است که بخاطرNP-Completeبودن ارائه یک الگوریتم تقریبی برای آن از اهمیت زیادی برخوردا راست دراین مسئله یک زنجیره باز n قسمتی به عنوان ورودی مفروض است و هدف یافتن کمترین طول ممکن برای تاک ردن زنجیره در فضای یک بعدی می باشد ما دراین مقاله یک الگوریتم تقریبی با زمان خطی و حافظه مصرفی O(1) برای تاکردن زنجیره ارائه کرده ایم که طول زنجیره تا شده را به حدی می رساند که نسبت به الگوریتم های قبلی از حد بالای کمتری برخوردار است این الگوریتم در نوع خود بهترین الگوریتم گزارش شده تقریبی با زمان خطی برای مسئله تاکردن خط کش می باشد.

مسئله تاکردن خط کش، زنجیره باز