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

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)

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

Cited in

(8)

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