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

Lehrstuhl für Angewandte Geometrie und Diskrete Mathematik

University of Siena
University of Groningen

Publikation: Beitrag in Fachzeitschrift › Artikel › Begutachtung

14 Zitate (Scopus)

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.

Originalsprache	Englisch
Seiten (von - bis)	63-71
Seitenumfang	9
Fachzeitschrift	Theoretical Computer Science
Jahrgang	406
Ausgabenummer	1-2
DOIs	https://doi.org/10.1016/j.tcs.2008.06.014
Publikationsstatus	Veröffentlicht - 28 Okt. 2008

Zugriff auf Dokument

10.1016/j.tcs.2008.06.014

Andere Dateien und Links

Verknüpfung zur Publikation in Scopus

Dieses zitieren

@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

Zugriff auf Dokument

Andere Dateien und Links

Fingerprint

Dieses zitieren