On the reconstruction of binary and permutation matrices under (binary) tomographic constraints

S. Brunetti; A. Del Lungo; P. Gritzmann; S. de Vries

doi:10.1016/j.tcs.2008.06.014

On the reconstruction of binary and permutation matrices under (binary) tomographic constraints

S. Brunetti
, A. Del Lungo
, P. Gritzmann
, S. de Vries

Chair of Geometry

University of Siena
University of Groningen

Research output: Contribution to journal › Article › peer-review

14 Scopus citations

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.

Original language	English
Pages (from-to)	63-71
Number of pages	9
Journal	Theoretical Computer Science
Volume	406
Issue number	1-2
DOIs	https://doi.org/10.1016/j.tcs.2008.06.014
State	Published - 28 Oct 2008

Keywords

Binary matrix
Bipartite matching
Combinatorics
Computational complexity
Contingency table
Discrete tomography
N P-hardness
Permutation
Queens' problem

Access to Document

10.1016/j.tcs.2008.06.014

Cite this

@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",

}

TY - JOUR

T1 - On the reconstruction of binary and permutation matrices under (binary) tomographic constraints

AU - Brunetti, S.

AU - Lungo, A. Del

AU - Gritzmann, P.

AU - de Vries, S.

N1 - 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.

PY - 2008/10/28

Y1 - 2008/10/28

N2 - 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.

AB - 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.

KW - Binary matrix

KW - Bipartite matching

KW - Combinatorics

KW - Computational complexity

KW - Contingency table

KW - Discrete tomography

KW - N P-hardness

KW - Permutation

KW - Queens' problem

UR - https://www.scopus.com/pages/publications/51549112708

U2 - 10.1016/j.tcs.2008.06.014

DO - 10.1016/j.tcs.2008.06.014

M3 - Article

AN - SCOPUS:51549112708

SN - 0304-3975

VL - 406

SP - 63

EP - 71

JO - Theoretical Computer Science

JF - Theoretical Computer Science

IS - 1-2

ER -

On the reconstruction of binary and permutation matrices under (binary) tomographic constraints

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this