Login
- Document type:
- Zeitschriftenaufsatz
- Author(s):
- Brunetti, S.; A. Del Lungo, P. Gritzmann and S. de Vries
- Title:
- On the reconstruction of binary and permutation matrices under (binary) tomographic constraints
- Abstract:
- The paper studies the problem of reconstructing binary matrices constrained by binary tomographic information. We prove new NP-hardness results that sharpen previous complexity results in the realm of discrete tomography but also allow applications to related problems for permutation matrices. Hence our results can be interpreted in terms of other combinatorial problems including the queens’ problem.
- Keywords:
- Combinatorics, Discrete tomography, Queens’ problem, Bipartite matching, Contingency table, Binary matrix, Permutation, Computational complexity, NP-hardness
- Journal title:
- Theoretical Computer Science
- Year:
- 2008
- Journal issue:
- 406
- Pages contribution:
- 63-71
- Reviewed:
- ja
- Language:
- en
- TUM Institution:
- Lehrstuhl für Angewandte Geometrie und Diskrete Mathematik
BibTeX