کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4951333 | 1441211 | 2016 | 12 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Reconstructing binary matrices with timetabling constraints
ترجمه فارسی عنوان
بازسازی ماتریسهای باینری با محدودیت زمانبندی
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
توموگرافی گسسته، مشکل بازسازی، پیچیدگی محاسباتی، برنامه ریزی مشکل
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
This paper deals with the reconstruction of binary matrices having specific local constraints, called Timetable Constraints, imposed on their elements. In the first part of the paper, we show that instances of this problem with some fixed parameters are solvable in linear time by means of a greedy approach. In the following, thanks to a slight relaxation of one of the Timetable Constraints, we define a second and more complex greedy algorithm that solves a much wider family of instances. In both of these cases the computational complexity of our algorithms is linear in the dimension of the reconstructed matrix. Finally, we complete the framework by proving that all but one the remaining cases are NP-complete.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Discrete Algorithms - Volumes 38â41, MayâNovember 2016, Pages 20-31
Journal: Journal of Discrete Algorithms - Volumes 38â41, MayâNovember 2016, Pages 20-31
نویسندگان
Srecko Brlek, Stefano Brocchi, Andrea Frosini,