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

RINALDI, SIMONE
2011-01-01

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.
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 Dimensione Formato  
2-color.pdf

non disponibili

Tipologia: Post-print
Licenza: NON PUBBLICO - Accesso privato/ristretto
Dimensione 278.46 kB
Formato Adobe PDF
278.46 kB Adobe PDF   Visualizza/Apri   Richiedi una copia

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11365/23049
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo