کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4952313 | 1442030 | 2017 | 7 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Vertex 2-coloring without monochromatic cycles of fixed size is NP-complete
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
In this paper we study a problem of vertex two-coloring of an undirected graph such that there is no monochromatic cycle of the given length. We show that this problem is hard to solve. We give a proof by presenting a reduction from the variation of satisfiability (SAT) problem. We show the nice properties of coloring cliques with two colors which plays pivotal role in the reduction construction.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 659, 10 January 2017, Pages 88-94
Journal: Theoretical Computer Science - Volume 659, 10 January 2017, Pages 88-94
نویسندگان
MichaÅ KarpiÅski,