Reconstruction of binary matrices under adjacency constraints

DOI10.1016/j.endm.2005.05.069zbMath1179.68181OpenAlexW4256128047MaRDI QIDQ3439193

Fethi Jarray, Marie-Christine Costa, Christophe Picouleau

Publication date: 29 May 2007

Published in: Electronic Notes in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.endm.2005.05.069

zbMATH Keywords

polynomial time algorithmNP-completediscrete tomographynetwork flowbinary matrix reconstructionadjacency constraint

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computing methodologies for image processing (68U10) Image processing (compression, reconstruction, etc.) in information and communication theory (94A08) Matrices of integers (15B36)

Related Items (2)

Reconstructing binary matrices with timetabling constraints ⋮ Binary image reconstruction based on prescribed numerical information

Cites Work

• Unnamed Item
• Unnamed Item
• Planar lattice gases with nearest-neighbor exclusion
• On tiling under tomographic constraints.
• Discrete tomography. Foundations, algorithms, and applications
• Reconstruction of convex 2D discrete sets in polynomial time
• Reconstruction of \(hv\)-convex binary matrices from their absorbed projections
• Combinatorial Properties of Matrices of Zeros and Ones
• The Number of Independent Sets in a Grid Graph
• Reconstruction of domino tiling from its two orthogonal projections
• Reconstructing polyatomic structures from discrete X-rays: NP-completeness proof for three atoms
• Reconstruction of discrete sets with absorption

This page was built for publication: Reconstruction of binary matrices under adjacency constraints