Reconstruction of Binary Matrices under Adjacency Constraints
Sara Brunetti, Martín Costa, Andrea Frosini, Fethi Jarray, Christophe Picouleau · Birkhäuser Boston eBooks · 2008
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. These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.