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

DOI10.1007/978-3-540-79126-3_35MaRDI QIDQ5458907zbMATH OpenOpenAlexFDO

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

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

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)

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