Abstract | ||
---|---|---|
In this paper we introduce a new class of binary matrices whose entries show periodical configurations, and we furnish a first approach to their analysis from a tomographical point of view. In particular we propose a polynomial-time algorithm for reconstructing matrices with a special periodical behavior from their horizontal and vertical projections. We succeeded in our aim by using a reduction involving polyominoes which can be characterized by means of 2 - SAT formulas. |
Year | DOI | Venue |
---|---|---|
2005 | 10.1016/j.tcs.2005.06.035 | Theor. Comput. Sci. |
Keywords | DocType | Volume |
binary matrix,Computational complexity,discrete set,tomographical point,SAT formula,new class,periodical configuration,special periodical behavior,polyomino,2 ¡ sat reduction.,polynomial-time algorithm,Polyomino,2 - SAT reduction,tomographical perspective,vertical projection,discrete tomography,Discrete tomography,computational complexity | Journal | 347 |
Issue | ISSN | Citations |
1-2 | Theoretical Computer Science | 7 |
PageRank | References | Authors |
0.66 | 11 | 3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Andrea Frosini | 1 | 101 | 20.44 |
Maurice Nivat | 2 | 1261 | 277.74 |
Laurent Vuillon | 3 | 186 | 26.63 |