@article{79d6e8b11af74eb48e49299754358bd9,
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 N P-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 = "Binary matrix, Bipartite matching, Combinatorics, Computational complexity, Contingency table, Discrete tomography, N P-hardness, Permutation, Queens' problem",
author = "S. Brunetti and Lungo, {A. Del} and P. Gritzmann and {de Vries}, S.",
note = "Funding Information: The present paper was supported by grant 31-vigoni-dr of the DAAD and grant vigoni-it of the CRUI. We thank the anonymous referees for some helpful remarks.",
year = "2008",
month = oct,
day = "28",
doi = "10.1016/j.tcs.2008.06.014",
language = "English",
volume = "406",
pages = "63--71",
journal = "Theoretical Computer Science",
issn = "0304-3975",
publisher = "Elsevier B.V.",
number = "1-2",
}