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

DOI10.1016/j.tcs.2008.06.014zbMath1160.68038OpenAlexW1982864005MaRDI QIDQ952460

Sara Brunetti, Alberto 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

combinatoricscomputational complexitypermutationNP-hardnessdiscrete tomographybipartite matchingbinary matrixcontingency tableQueens' problem

Mathematics Subject Classification ID

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

Related Items

On bounded additivity in discrete tomography, Complexity results for reconstructing binary images with disjoint components from horizontal and vertical projections, On vanishing of Kronecker coefficients, On polyatomic tomography over abelian groups: some remarks on consistency, tree packings and complexity, Complexity of and algorithms for the manipulation of Borda, Nanson's and Baldwin's voting rules, Dynamic discrete tomography, On the computational complexity of reconstructing three-dimensional lattice sets from their two-dimensional \(X\)-rays, On the X-rays of permutations, Reconstructing permutation matrices from diagonal sums, Binary image reconstruction based on prescribed numerical information

Cites Work

• Unnamed Item
• Unnamed Item
• On the computational complexity of reconstructing lattice sets from their \(X\)-rays
• Discrete tomography. Foundations, algorithms, and applications
• On the algorithmic inversion of the discrete Radon transform
• On the Complexity of Timetable and Multicommodity Flow Problems
• Three-dimensional Statistical Data Security Problems
• On the computational complexity of reconstructing three-dimensional lattice sets from their two-dimensional \(X\)-rays