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
BibTeX