کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4951259 | 1441199 | 2017 | 12 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
On the parameterized complexity of b-chromatic number
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
The b-chromatic number of a graph G, Ïb(G), is the largest integer k such that G has a k-vertex coloring with the property that each color class has a vertex which is adjacent to at least one vertex in each of the other color classes. In the b-Chromatic Number problem, the objective is to decide whether Ïb(G)â¥k. Testing whether Ïb(G)=Î(G)+1, where Î(G) is the maximum degree of a graph, itself is NP-complete even for connected bipartite graphs (KratochvÃl, Tuza and Voigt, WG 2002). We show that b-Chromatic Number is W[1]-hard when parameterized by k, resolving the open question posed by Havet and Sampaio (Algorithmica 2013). When k=Î(G)+1, we design an algorithm for b-Chromatic Number running in time 2O(k2logâ¡k)nO(1). Finally, we show that b-Chromatic Number for an n-vertex graph can be solved in time O(3nn4logâ¡n).
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Computer and System Sciences - Volume 84, March 2017, Pages 120-131
Journal: Journal of Computer and System Sciences - Volume 84, March 2017, Pages 120-131
نویسندگان
Fahad Panolan, Geevarghese Philip, Saket Saurabh,