User: Guest  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