کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
9655860 | 685323 | 2005 | 15 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
On-line Chain Partitioning as a Model for Real-time Scheduling
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
We consider on-line chain partitioning of a poset as a theoretical model for some variant of tasks scheduling. Restricting ourselves to interval orders given by its representation the problem is equivalent to the coloring problem of interval graphs. We prove that up-growing variant of on-line chain partitioning of interval orders given by its representation has an optimal solution (Nearest-Fit algorithm). We also consider on-line chain partitioning of interval orders without representation and prove the lower bound for the up-growing version (3w/2). Moreover we show that there is no on-line algorithm constructing the representation of interval orders and graphs.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Electronic Notes in Theoretical Computer Science - Volume 140, 18 November 2005, Pages 15-29
Journal: Electronic Notes in Theoretical Computer Science - Volume 140, 18 November 2005, Pages 15-29
نویسندگان
Przemyslaw Broniek,