کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4951225 | 1441196 | 2017 | 15 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
On planar valued CSPs
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
We study the computational complexity of planar valued constraint satisfaction problems (VCSPs), which require the incidence graph of the instance be planar. First, we show that intractable Boolean VCSPs have to be self-complementary to be tractable in the planar setting, thus extending a corresponding result of DvoÅák and Kupec [ICALP'15] from CSPs to VCSPs. Second, we give a complete complexity classification of conservative planar VCSPs on arbitrary finite domains. In this case planarity does not lead to any new tractable cases and thus our classification is a sharpening of the classification of conservative VCSPs by Kolmogorov and Živný [JACM'13].
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Computer and System Sciences - Volume 87, August 2017, Pages 104-118
Journal: Journal of Computer and System Sciences - Volume 87, August 2017, Pages 104-118
نویسندگان
Peter Fulla, Stanislav Živný,