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

作者：Brocchi S; Frosini A^*; Rinaldi S

来源：Theoretical Computer Science, 2011, 412(36): 4795-4804.

DOI：10.1016/j.tcs.2010.08.004

• Discrete tomography
• Polynomial time algorithm
• c-color problem

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.

• 出版日期2011-8-19