کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
418828 | 681720 | 2009 | 8 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Extension problems with degree bounds
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
We have proved in an earlier paper that the complexity of the list homomorphism problem, to a fixed graph HH, does not change when the input graphs are restricted to have bounded degrees (except in the trivial case when the bound is two). By way of contrast, we show in this paper that the extension problem, again to a fixed graph HH, can, in some cases, become easier for graphs with bounded degrees.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 157, Issue 7, 6 April 2009, Pages 1592–1599
Journal: Discrete Applied Mathematics - Volume 157, Issue 7, 6 April 2009, Pages 1592–1599
نویسندگان
Tomas Feder, Pavol Hell, Jing Huang,