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)

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

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)