کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
10328517 684040 2005 5 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
On approximating the b-chromatic number
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
On approximating the b-chromatic number
چکیده انگلیسی
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
نویسندگان
, , ,