Reconstruction of binary matrices under adjacency constraints

DOI10.1016/J.ENDM.2005.05.069MaRDI QIDQ3439193zbMATH OpenOpenAlexFDO

Authors Marie-Christine Costa, Fethi Jarray, 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

network flowdiscrete tomographyNP-completepolynomial time algorithmbinary matrix reconstructionadjacency constraint

Mathematics Subject Classification ID

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

Recommendations

• Reconstruction of binary matrices under adjacency constraints
• Reconstruction of binary matrices under fixed size neighborhood constraints
• Reconstructing Binary Matrices with Neighborhood Constraints: An NP-hard Problem
• scientific article; zbMATH DE number 809139
• Reconstructing binary matrices under window constraints from their row and column sums
• A greedy algorithm for reconstructing binary matrices with adjacent 1s
• scientific article; zbMATH DE number 2087481
• On the reconstruction of binary and permutation matrices under (binary) tomographic constraints
• Reconstructing binary matrices with timetabling constraints
• Reconstructing a binary matrix under timetabling constraints

Cites work

• scientific article; zbMATH DE number 2086609 (Why is no real title available?)
• Combinatorial Properties of Matrices of Zeros and Ones
• Discrete tomography. Foundations, algorithms, and applications
• Network flows. Theory, algorithms, and applications.
• On tiling under tomographic constraints.
• Planar lattice gases with nearest-neighbor exclusion
• Reconstructing polyatomic structures from discrete X-rays: NP-completeness proof for three atoms
• Reconstruction of \(hv\)-convex binary matrices from their absorbed projections
• Reconstruction of convex 2D discrete sets in polynomial time
• Reconstruction of discrete sets with absorption
• Reconstruction of domino tiling from its two orthogonal projections
• The Number of Independent Sets in a Grid Graph

Cited in

(12)

• Reconstructing a binary matrix under timetabling constraints
• On the reconstruction of binary and permutation matrices under (binary) tomographic constraints
• A greedy algorithm for reconstructing binary matrices with adjacent 1s
• Reconstructing binary matrices under window constraints from their row and column sums
• Reconstructing (0,1)-matrices from projections using integer programming
• Binary image reconstruction based on prescribed numerical information
• scientific article; zbMATH DE number 809139 (Why is no real title available?)
• Reconstructing binary matrices with timetabling constraints
• Reconstruction of binary matrices under adjacency constraints
• Reconstruction of binary matrices under fixed size neighborhood constraints
• Theoretical Computer Science
• Reconstructing Binary Matrices with Neighborhood Constraints: An NP-hard Problem

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3439193)