کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
10328517 | 684040 | 2005 | 5 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
On approximating the b-chromatic number
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله

چکیده انگلیسی
We consider the problem of approximating the b-chromatic number of a graph. We show that there is no constant É>0 for which this problem can be approximated within a factor of 120/133-É in polynomial time, unless P=NP. This is the first hardness result for approximating the b-chromatic number.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 146, Issue 1, 15 February 2005, Pages 106-110
Journal: Discrete Applied Mathematics - Volume 146, Issue 1, 15 February 2005, Pages 106-110
نویسندگان
Sylvie Corteel, Mario Valencia-Pabon, Juan-Carlos Vera,