Reconstruction of Binary Matrices under Adjacency Constraints.

We are concerned with binary matrix reconstruction from their orthogonal projections. To the basic problem we add new kinds of constraints. In the first problems we study the ones of the matrix must be isolated: All the neighbors of a one must be a zero. Several types of neighborhoods are studied. In our second problem, every one has to be horizontally not isolated. Moreover, the number of successive zeros in a horizontal rank must be bounded by a fixed parameter. Complexity results and polynomial-time algorithms are given. [ABSTRACT FROM AUTHOR]