Article ID: | iaor20119256 |
Volume: | 39 |
Issue: | 5 |
Start Page Number: | 346 |
End Page Number: | 351 |
Publication Date: | Sep 2011 |
Journal: | Operations Research Letters |
Authors: | Niedermeier Rolf, Nichterlein Andr, Dom Michael |
Keywords: | complexity |
We identify very restricted cases of Rectangle Tiling that remain NP‐hard. Tiling binary matrices with squares is NP‐hard. We describe efficient algorithms when the number of rectangles is small. Research challenges for the parameterized complexity of Rectangle Tiling are listed.