Reconstruction of binary matrices under fixed size neighborhood constraints

DOI10.1016/J.TCS.2008.07.024zbMath1160.68037OpenAlexW1982314155MaRDI QIDQ952456

Christophe Picouleau, Stefano Brocchi, Andrea Frosini

Publication date: 12 November 2008

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2008.07.024

zbMATH Keywords

dynamic programmingNP-completenessdiscrete tomographyparameterized complexitybinary matrix reconstruction

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorial aspects of matrices (incidence, Hadamard, etc.) (05B20) Dynamic programming (90C39) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (7)

Reconstructing binary matrices with timetabling constraints ⋮ A reconstruction algorithm for a subclass of instances of the 2-color problem ⋮ Solving the Two Color Problem: An Heuristic Algorithm ⋮ On the use of graphs in discrete tomography ⋮ On the use of graphs in discrete tomography ⋮ Solving Some Instances of the 2-Color Problem ⋮ Binary image reconstruction based on prescribed numerical information

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Reconstructing convex polyominoes from horizontal and vertical projections
• Planar lattice gases with nearest-neighbor exclusion
• Tiling with bars under tomographic constraints.
• On tiling under tomographic constraints.
• Discrete tomography. Foundations, algorithms, and applications
• The reconstruction of polyominoes from their orthogonal projections
• Reconstruction of convex 2D discrete sets in polynomial time
• A solvable case of image reconstruction in discrete tomography
• An introduction to periodical discrete sets from a tomographical perspective
• Using graphs for some discrete tomography problems
• Advances in discrete tomography and its applications. Some papers based on the presentations at the workshop on discrete tomography and its applications, New York, NY, USA, June 13--15, 2005.
• Combinatorial Properties of Matrices of Zeros and Ones
• Theoretical Computer Science
• Reconstruction of domino tiling from its two orthogonal projections
• Reconstructing polyatomic structures from discrete X-rays: NP-completeness proof for three atoms
• Reconstruction of 4- and 8-connected convex discrete sets from row and column projections

This page was built for publication: Reconstruction of binary matrices under fixed size neighborhood constraints