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

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

Christophe Picouleau, S. Rinaldi, Andrea Frosini

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)

Cited In (4)

• Reconstructing a binary matrix under timetabling constraints
• Reconstruction of binary matrices under adjacency constraints
• Regular switching components
• Reconstruction of binary matrices under fixed size neighborhood constraints

   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 👍 👎

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)