کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4650831 | 1342504 | 2007 | 12 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Complexity issues on bounded restrictive H-coloring
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله

چکیده انگلیسی
We consider a bounded version of the restrictive and the restrictive list H-coloring problem in which the number of pre-images of certain vertices of H is taken as parameter. We consider the decision and the counting versions, as well as, further variations of those problems. We provide complexity results identifying the cases when the problems are NP-complete or #P-complete or polynomial time solvable. We conclude stating some open problems.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 307, Issue 16, 28 July 2007, Pages 2082–2093
Journal: Discrete Mathematics - Volume 307, Issue 16, 28 July 2007, Pages 2082–2093
نویسندگان
Josep Díaz, Maria Serna, Dimitrios M. Thilikos,