کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6424056 | 1632767 | 2016 | 19 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
First-fit coloring on interval graphs has performance ratio at least 5
ترجمه فارسی عنوان
اولویت رنگ آمیزی بر روی نمودارهای فاصله دارای نسبت کارایی حداقل 5 است
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
چکیده انگلیسی
First-fit is the online graph coloring algorithm that considers vertices one at a time in some order and assigns each vertex the least positive integer not used already on a neighbor. The maximum number of colors used by first-fit on graph G over all vertex orders is denoted ÏFF(G).The exact value of R:=supGÏFF(G)Ï(G) over interval graphs G is unknown. Pemmaraju, Raman, and Varadarajan (2004) proved Râ¤10, and this can be improved to 8. Witsenhausen (1976) and Chrobak and Ålusarek (1988) showed Râ¥4, and Ålusarek (1993) improved this to 4.45. We prove Râ¥5.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: European Journal of Combinatorics - Volume 51, January 2016, Pages 236-254
Journal: European Journal of Combinatorics - Volume 51, January 2016, Pages 236-254
نویسندگان
H.A. Kierstead, David A. Smith, W.T. Trotter,