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

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

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)

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

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)