Reconstructing binary matrices under window constraints from their row and column sums

DOI10.3233/FI-2017-1588MaRDI QIDQ4599798zbMATH OpenOpenAlexFDO

Authors Andreas Alpers, Peter Gritzmann

Publication date 5 January 2018

Published in Fundamenta Informaticae (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1702.06121

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorics in computer science (68R05) Computing methodologies for image processing (68U10) Combinatorial aspects of matrices (incidence, Hadamard, etc.) (05B20)

Abstract: The present paper deals with the discrete inverse problem of reconstructing binary matrices from their row and column sums under additional constraints on the number and pattern of entries in specified minors. While the classical consistency and reconstruction problems for two directions in discrete tomography can be solved in polynomial time, it turns out that these window constraints cause various unexpected complexity jumps back and forth from polynomial-time solvability to $mathbbNmathbbP$-hardness.

Recommendations

• 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
• scientific article; zbMATH DE number 2086609
• Reconstruction of binary matrices under adjacency constraints

Cited in

(15)

• Reconstructing a binary matrix under timetabling constraints
• Weighted microscopic image reconstruction
• Binary matrices under the microscope: A tomographical problem
• Scanning integer matrices by means of two rectangular windows
• Weighted microscopic image reconstruction
• Relaxed and approximate graph realizations
• On the reconstruction of binary and permutation matrices under (binary) tomographic constraints
• On double-resolution imaging and discrete tomography
• Convex \((0, 1)\)-matrices and their epitopes
• Reconstruction of binary matrices under adjacency constraints
• The generalized microscopic image reconstruction problem
• scientific article; zbMATH DE number 2086609 (Why is no real title available?)
• Reconstruction of binary matrices under fixed size neighborhood constraints
• Dynamic discrete tomography
• On polyatomic tomography over abelian groups: some remarks on consistency, tree packings and complexity

This page was built for publication: Reconstructing binary matrices under window constraints from their row and column sums

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