کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
420113 683895 2011 13 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
The external constraint 4 nonempty part sandwich problem
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
The external constraint 4 nonempty part sandwich problem
چکیده انگلیسی

List partitions generalize list colourings. Sandwich problems generalize recognition problems. The polynomial dichotomy (NP-complete versus polynomial) of list partition problems is solved for 4-dimensional partitions with the exception of one problem (the list stubborn problem) for which the complexity is known to be quasipolynomial. Every partition problem for 4 nonempty parts and only external constraints is known to be polynomial with the exception of one problem (the 2K22K2-partition problem) for which the complexity of the corresponding list problem is known to be NP-complete. The present paper considers external constraint 4 nonempty part sandwich problems. We extend the tools developed for polynomial solutions of recognition problems obtaining polynomial solutions for most corresponding sandwich versions. We extend the tools developed for NP-complete reductions of sandwich partition problems obtaining the classification into NP-complete for some external constraint 4 nonempty part sandwich problems. On the other hand and additionally, we propose a general strategy for defining polynomial reductions from the 2K22K2-partition problem to several external constraint 4 nonempty part sandwich problems, defining a class of 2K22K2-hard problems. Finally, we discuss the complexity of the Skew Partition Sandwich Problem.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 159, Issue 7, 6 April 2011, Pages 661–673
نویسندگان
, , ,