کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
419834 | 683866 | 2008 | 19 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
The stack loading and unloading problem
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
When piling a set of items in a single stack, one often does not pay attention to the order. Real-life experience suggests that, whenever a specific item is suddenly requested, we need to dig very deep into the stack to extract it.In this paper we investigate stack reordering strategies aiming at minimizing the number of pop and push operations. In particular we focus on three versions of the problem in which reordering can take place in different phases: when unloading the stack, when loading it or in both phases. We show that the first two variants can be solved in linear time, while for the third one we devise a dynamic programming method with quadratic complexity.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 156, Issue 17, 28 October 2008, Pages 3248–3266
Journal: Discrete Applied Mathematics - Volume 156, Issue 17, 28 October 2008, Pages 3248–3266
نویسندگان
Federico Malucelli, Stefano Pallottino, Daniele Pretolani,