On the reconstruction of binary and permutation matrices under (binary) tomographic constraints

DOI10.1016/J.TCS.2008.06.014MaRDI QIDQ952460zbMATH OpenOpenAlexFDO

Authors S. Brunetti, A. Del Lungo, Peter Gritzmann, Sven De Vries

Publication date 12 November 2008

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2008.06.014

zbMATH Keywords

binary matrixbipartite matchingcombinatoricscomputational complexitycontingency tablediscrete tomographyNP-hardnesspermutationQueens' problem

Mathematics Subject Classification ID

Combinatorial aspects of matrices (incidence, Hadamard, etc.) (05B20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Recommendations

• Reconstructing Binary Matrices with Neighborhood Constraints: An NP-hard Problem
• Reconstructing binary matrices under window constraints from their row and column sums
• Reconstruction of binary matrices under adjacency constraints
• Reconstruction of binary matrices under fixed size neighborhood constraints
• Reconstruction of binary matrices under adjacency constraints

Cites work

• Discrete tomography. Foundations, algorithms, and applications
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 900396 (Why is no real title available?)
• On the algorithmic inversion of the discrete Radon transform
• On the Complexity of Timetable and Multicommodity Flow Problems
• On the computational complexity of reconstructing lattice sets from their X-rays
• On the computational complexity of reconstructing three-dimensional lattice sets from their two-dimensional X-rays
• Three-dimensional Statistical Data Security Problems

Cited in

(17)

• Reconstructing permutation matrices from diagonal sums
• On vanishing of Kronecker coefficients
• On polyatomic tomography over abelian groups: some remarks on consistency, tree packings and complexity
• Binary image reconstruction based on prescribed numerical information
• On bounded additivity in discrete tomography
• On the X-rays of permutations
• Reconstruction of binary matrices under adjacency constraints
• Complexity results for reconstructing binary images with disjoint components from horizontal and vertical projections
• Reconstructing binary matrices under window constraints from their row and column sums
• Dynamic discrete tomography
• Complexity of and algorithms for the manipulation of Borda, Nanson's and Baldwin's voting rules
• Theoretical Computer Science
• Reconstructing Binary Matrices with Neighborhood Constraints: An NP-hard Problem
• Combinatorial Image Analysis
• Theory Is Forever
• On the computational complexity of reconstructing three-dimensional lattice sets from their two-dimensional X-rays
• Reconstruction of binary matrices under fixed size neighborhood constraints

This page was built for publication: On the reconstruction of binary and permutation matrices under (binary) tomographic constraints

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