In the field of Discrete Tomography, the 2-color problem consists in reconstructing a matrix whose elements are of two different types, starting from its horizontal and vertical projections. It is known that the 1-color problem admits a polynomial time reconstruction algorithm, while the c-color problem, with c ≥ 2, is NP-hard. Thus, the 2-color problem constitutes an interesting example of a problem just in the frontier between hard and easy problems. In this paper we define a linear time algorithm (in the size of the output matrix) to solve a subclass of its instances, where some values of the horizontal and vertical projections are constant, while the others are upper bounded by a positive number proportional to the dimension of the problem. Our algorithm relies on classical studies for the solution of the 1-color problem.

Brocchi, S., Frosini, A., Rinaldi, S. (2011). A reconstruction algorithm for a subclass of instances of the 2-color problem. THEORETICAL COMPUTER SCIENCE, 36, 4795-4804.

### A reconstruction algorithm for a subclass of instances of the 2-color problem

#### Abstract

In the field of Discrete Tomography, the 2-color problem consists in reconstructing a matrix whose elements are of two different types, starting from its horizontal and vertical projections. It is known that the 1-color problem admits a polynomial time reconstruction algorithm, while the c-color problem, with c ≥ 2, is NP-hard. Thus, the 2-color problem constitutes an interesting example of a problem just in the frontier between hard and easy problems. In this paper we define a linear time algorithm (in the size of the output matrix) to solve a subclass of its instances, where some values of the horizontal and vertical projections are constant, while the others are upper bounded by a positive number proportional to the dimension of the problem. Our algorithm relies on classical studies for the solution of the 1-color problem.
##### Scheda breve Scheda completa Scheda completa (DC) Brocchi, S., Frosini, A., Rinaldi, S. (2011). A reconstruction algorithm for a subclass of instances of the 2-color problem. THEORETICAL COMPUTER SCIENCE, 36, 4795-4804.
File in questo prodotto:
File
2-color.pdf

non disponibili

Tipologia: Post-print
Licenza: NON PUBBLICO - Accesso privato/ristretto
Dimensione 278.46 kB
Utilizza questo identificativo per citare o creare un link a questo documento: `https://hdl.handle.net/11365/23049`