کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
428109 | 686601 | 2009 | 6 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
There are no pure relational width 2 constraint satisfaction problems
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله

چکیده انگلیسی
In this note, we show that every constraint satisfaction problem that has relational width 2 has also relational width 1. This is achieved by means of an obstruction-like characterization of relational width which we believe to be of independent interest.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information Processing Letters - Volume 109, Issue 4, 31 January 2009, Pages 213-218
Journal: Information Processing Letters - Volume 109, Issue 4, 31 January 2009, Pages 213-218