Reconstructing Binary Matrices with Neighborhood Constraints: An NP-hard Problem

DOI10.1007/978-3-540-79126-3_35zbMATH Open1138.68574OpenAlexW1540286128MaRDI QIDQ5458907FDOQ5458907

Authors: S. Rinaldi, Andrea Frosini, Christophe Picouleau 

Publication date: 24 April 2008

Published in: Discrete Geometry for Computer Imagery (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-79126-3_35

Recommendations

• Reconstruction of binary matrices under adjacency constraints
• Reconstruction of binary matrices under adjacency constraints
• Reconstruction of binary matrices under fixed size neighborhood constraints
• A greedy algorithm for reconstructing binary matrices with adjacent 1s
• On the reconstruction of binary and permutation matrices under (binary) tomographic constraints

zbMATH Keywords

discrete tomographyNP-complete problempolynomial-time reduction

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Computing methodologies for image processing (68U10) Machine vision and scene understanding (68T45)

Cited In (8)

• Reconstructing a binary matrix under timetabling constraints
• A greedy algorithm for reconstructing binary matrices with adjacent 1s
• On the reconstruction of binary and permutation matrices under (binary) tomographic constraints
• Reconstruction of binary matrices under adjacency constraints
• Reconstructing 3-Colored Grids from Horizontal and Vertical Projections Is NP-hard
• Reconstruction of binary matrices under adjacency constraints
• Regular switching components
• Reconstruction of binary matrices under fixed size neighborhood constraints

This page was built for publication: Reconstructing Binary Matrices with Neighborhood Constraints: An NP-hard Problem

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