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 prodotto non validato
Scheda prodotto in fase di analisi da parte dello staff di validazione
|Titolo:||A reconstruction algorithm for a subclass of instances of the 2-color problem|
|Citazione:||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.|
|Appare nelle tipologie:||1.1 Articolo in rivista|