# [BCF07] Reconstruction of binary matrices under adjacency constraints

**Chapitres de Livre : **
Titre du livre: "

*Advances in Discrete Tomography and Its Applications*",
July 2007,
Birkhauser/Gabor and Attila,

pp. 125-150,
(

isbn: 978-0-8176-3614-2)

**motcle: **

**Résumé: **
Given a binary matrix, its horizontal and vertical projections are defined as
the sum of its elements for each row and each column, respectively. It is well-known that the basic problem,
where the only constraints to verify are both projections, can be solved in
polynomial time. Numerous studies deal with this problem when additional
constraints have to be taken into account. In this chapter we study two
additional constraints for this problem. In a first part we take into account the
non-adjacency constraint that depends on the definition of neighborhood:
if a cell value is 1, then the values of each one of its neighbors must be 0. This
problem arises especially in statistical physics to determine the microscopic
properties (energy, density, entropy). In the model of Hard Square Gas, two
adjacent cells cannot be occupied simultaneously by particles because the energy
of repulsion between them is very high.
In the second part, we are concerned with a different constraint that imposes
that in every row of the binary matrix no isolated cell with value 1 is
permitted, and the maximum number of consecutive cells of value 0 is not
greater than a prescribed integer k. Taking into account this constraint, the
reconstruction of binary matrices has natural applications in timetabling and
workforce scheduling.