Reconstructing a binary matrix under timetabling constraints

Our focus is on the problem of reconstructing a m × n binary matrix M from its vertical and horizontal projections when the following additional constraints have to be satisfied: given an integer k ⩾ 2 , if M i j = 1 then M i j − 1 = 1 or M i j + 1 = 1 , and the maximal number of successive 0ʹs on each row of M is not greater than k. We furnish a polynomial time algorithm for reconstructing M by reducing this problem to that of finding a path of given weight in a weighted directed acyclic graph.