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

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