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 (10)

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

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