Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
9514631 | Electronic Notes in Discrete Mathematics | 2005 | 14 Pages |
Abstract
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 Mij=1 then Mijâ1=1 or Mij+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.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
C. Picouleau, S. Brunetti, A. Frosini,