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

DOI10.3233/FI-2017-1588zbMATH Open1377.68155arXiv1702.06121OpenAlexW2593188018MaRDI QIDQ4599798FDOQ4599798

Authors: Andreas Alpers, Peter Gritzmann 

Publication date: 5 January 2018

Published in: Fundamenta Informaticae (Search for Journal in Brave)

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.

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

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

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)

Cited In (15)

• Reconstructing a binary matrix under timetabling constraints
• Weighted microscopic image reconstruction
• Weighted microscopic image reconstruction
• Binary matrices under the microscope: A tomographical problem
• Scanning integer matrices by means of two rectangular windows
• 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
• Title not available (Why is that?)
• Dynamic discrete tomography
• Reconstruction of binary matrices under fixed size neighborhood constraints
• 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)