کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
5777430 | 1632755 | 2017 | 20 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Hardness of computing clique number and chromatic number for Cayley graphs
ترجمه فارسی عنوان
سختی محاسبه تعداد کل و تعداد رنگی برای نمودارهای کایلی
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
چکیده انگلیسی
Computing the clique number and chromatic number of a general graph are well-known NP-Hard problems. Codenotti et al., (1998) showed that computing clique number and chromatic number are both NP-Hard problems for the class of circulant graphs. We show that computing clique number is NP-Hard for the class of Cayley graphs for the groups Gn, where G is any fixed finite group (e.g., cubelike graphs). We also show that computing chromatic number cannot be done in polynomial time (under the assumption NPâ ZPP) for the same class of graphs. Our presentation uses free Cayley graphs. The proof combines free Cayley graphs with quotient graphs and Goppa codes.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: European Journal of Combinatorics - Volume 62, May 2017, Pages 147-166
Journal: European Journal of Combinatorics - Volume 62, May 2017, Pages 147-166
نویسندگان
Chris Godsil, Brendan Rooney,