Name
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. |
Year | DOI | Venue |
|---|---|---|
2013 | 10.1016/j.jcta.2013.06.008 | Journal of Combinatorial Theory, Series A |
Keywords | DocType | Volume |
Tiling,Rectangles,NP-completeness,#P-completeness | Journal | 120 |
Issue | ISSN | Citations |
7 | 0097-3165 | 4 |
PageRank | References | Authors |
0.49 | 19 | 2 |