Name
Abstract | ||
|---|---|---|
In the field of Discrete Tomography, the 2-color problem consists in determining a matrix whose elements are of two different types, starting from its horizontal and vertical projections. It is known that the one color problem has a polynomial time reconstruction algorithm, while, with k ≥ 2, the k-color problem is NP-complete. 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 to solve a set 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 one color problem. |
Year | DOI | Venue |
|---|---|---|
2009 | 10.1007/978-3-642-04397-0_43 | DGCI |
Keywords | Field | DocType |
color problem,discrete tomography,linear time algorithm,2-color problem,vertical projection,classical study,easy problem,different type,polynomial time reconstruction algorithm,k-color problem,upper bound,polynomial time | Discrete mathematics,Combinatorics,Algorithmics,Computer science,co-NP-complete,P versus NP problem,Cutting stock problem,Vertex cover,Function problem,Multi-commodity flow problem,Polynomial-time reduction | Conference |
Volume | ISSN | ISBN |
5810 | 0302-9743 | 3-642-04396-8 |
Citations | PageRank | References |
3 | 0.41 | 7 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| S. Brocchi | 1 | 18 | 3.94 |
| A. Frosini | 2 | 15 | 2.49 |
| Simone Rinaldi | 3 | 174 | 24.93 |