Article ID Journal Published Year Pages File Type
4951333 Journal of Discrete Algorithms 2016 12 Pages PDF
Abstract
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.
Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
, , ,