کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
1142624 | 957158 | 2011 | 6 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Aspects of a multivariate complexity analysis for Rectangle Tiling
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
![عکس صفحه اول مقاله: Aspects of a multivariate complexity analysis for Rectangle Tiling Aspects of a multivariate complexity analysis for Rectangle Tiling](/preview/png/1142624.png)
چکیده انگلیسی
We initiate a parameterized complexity study of the NP-hard problem to tile a positive integer matrix with rectangles, keeping the number of tiles and their maximum weight small. We show that the problem remains NP-hard even for binary matrices only using 1×1 and 2×2-squares as tiles and provide insight into the influence of naturally occurring parameters on the problem’s 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.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Operations Research Letters - Volume 39, Issue 5, September 2011, Pages 346–351
Journal: Operations Research Letters - Volume 39, Issue 5, September 2011, Pages 346–351
نویسندگان
André Nichterlein, Michael Dom, Rolf Niedermeier,