کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4655439 1343384 2013 13 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Tiling simply connected regions with rectangles
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
Tiling simply connected regions with rectangles
چکیده انگلیسی

In 1995, Beauquier, Nivat, Rémila, and Robson showed that tiling of general regions with two bars is NP-complete, except for a few trivial special cases. In a different direction, in 2005, Rémila showed that for simply connected regions by two rectangles, the tileability can be solved in quadratic time (in the area). We prove that there is a finite set of at most 106 rectangles for which the tileability problem of simply connected regions is NP-complete, closing the gap between positive and negative results in the field. We also prove that counting such rectangular tilings is #P-complete, a first result of this kind.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Combinatorial Theory, Series A - Volume 120, Issue 7, September 2013, Pages 1804–1816
نویسندگان
, ,