کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
420773 | 683977 | 2008 | 4 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
On the restricted homomorphism problem
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
![عکس صفحه اول مقاله: On the restricted homomorphism problem On the restricted homomorphism problem](/preview/png/420773.png)
چکیده انگلیسی
The restricted homomorphism problem RHP(H,Y) asks: given an input digraph GG and a homomorphism g:G→Yg:G→Y, does there exist a homomorphism f:G→Hf:G→H? We prove that if HH is hereditarily hard and Y↛HY↛H, then RHP(H,Y) is NP-complete. Since non-bipartite graphs are hereditarily hard, this settles in the affirmative a conjecture of Hell and Nešetřil.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 156, Issue 14, 28 July 2008, Pages 2823–2826
Journal: Discrete Applied Mathematics - Volume 156, Issue 14, 28 July 2008, Pages 2823–2826
نویسندگان
Richard C. Brewster, Timothy Graves,