Name
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. |
Year | DOI | Venue |
|---|---|---|
2011 | 10.1016/j.tcs.2010.08.004 | Theor. Comput. Sci. |
Keywords | DocType | Volume |
Discrete Tomography,linear time algorithm,2-color problem,vertical projection,classical study,Polynomial time algorithm,Discrete tomography,1-color problem,easy problem,polynomial time reconstruction algorithm,c-color problem,output matrix | Journal | 412 |
Issue | ISSN | Citations |
36 | Theoretical Computer Science | 4 |
PageRank | References | Authors |
0.44 | 7 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| S. Brocchi | 1 | 18 | 3.94 |
| A. Frosini | 2 | 19 | 3.03 |
| Simone Rinaldi | 3 | 174 | 24.93 |