کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
418379 | 681656 | 2013 | 4 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
A note on approximating the bb-chromatic number
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
![عکس صفحه اول مقاله: A note on approximating the bb-chromatic number A note on approximating the bb-chromatic number](/preview/png/418379.png)
چکیده انگلیسی
We consider the problem of approximating the bb-chromatic number of a graph. In 2005, Corteel et al. proved that there is no constant ϵ>0ϵ>0 for which this problem can be approximated within a factor of 120/113−ϵ120/113−ϵ in polynomial time, unless P=NPP=NP. An existence of a constant-factor approximation algorithm for the bb-chromatic number in general graphs was formulated as an open problem.In this paper we settle this question in a negative way proving that there is no constant ϵ>0ϵ>0, for which the problem can be approximated within a factor n1/4−ϵn1/4−ϵ, unless P=NPP=NP.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 161, Issues 7–8, May 2013, Pages 1137–1140
Journal: Discrete Applied Mathematics - Volume 161, Issues 7–8, May 2013, Pages 1137–1140
نویسندگان
František Galčík, Ján Katrenič,