Title of article :
Tiling simply connected regions with rectangles
Author/Authors :
Pak، نويسنده , , Igor and Yang، نويسنده , , Jed، نويسنده ,
Issue Information :
روزنامه با شماره پیاپی سال 2013
Pages :
13
From page :
1804
To page :
1816
Abstract :
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.
Keywords :
Tiling , NP-Completeness , Rectangles , #P-completeness
Journal title :
Journal of Combinatorial Theory Series A
Serial Year :
2013
Journal title :
Journal of Combinatorial Theory Series A
Record number :
1531945
Link To Document :
بازگشت