Benutzer: Gast  Login
Dokumenttyp:
Zeitschriftenaufsatz 
Autor(en):
Brunetti, S.; A. Del Lungo, P. Gritzmann and S. de Vries 
Titel:
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. 
Stichworte:
Combinatorics, Discrete tomography, Queens’ problem, Bipartite matching, Contingency table, Binary matrix, Permutation, Computational complexity, NP-hardness 
Zeitschriftentitel:
Theoretical Computer Science 
Jahr:
2008 
Heft / Issue:
406 
Seitenangaben Beitrag:
63-71 
Reviewed:
ja 
Sprache:
en 
TUM Einrichtung:
Lehrstuhl für Angewandte Geometrie und Diskrete Mathematik