Reconstructing Binary Matrices underWindow Constraints from their Row and Column Sums

Andreas Alpers; Peter Gritzmann

doi:10.3233/FI-2017-1588

Reconstructing Binary Matrices underWindow Constraints from their Row and Column Sums

Andreas Alpers
, Peter Gritzmann

Chair of Geometry

Technical University of Munich

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

9 Scopus citations

Abstract

The present paper deals with the discrete inverse problem of reconstructing binary matrices from their row and column sums under additional constraints on the number and pattern of entries in specified minors. While the classical consistency and reconstruction problems for two directions in discrete tomography can be solved in polynomial time, it turns out that these window constraints cause various unexpected complexity jumps back and forth from polynomialtime solvability to NP-hardness.

Original language	English
Pages (from-to)	321-340
Number of pages	20
Journal	Fundamenta Informaticae
Volume	155
Issue number	4
DOIs	https://doi.org/10.3233/FI-2017-1588
State	Published - 2017

Access to Document

10.3233/FI-2017-1588

Cite this

@article{422ca15b449848cc9c19174e8a1f96ca,

title = "Reconstructing Binary Matrices underWindow Constraints from their Row and Column Sums",

abstract = "The present paper deals with the discrete inverse problem of reconstructing binary matrices from their row and column sums under additional constraints on the number and pattern of entries in specified minors. While the classical consistency and reconstruction problems for two directions in discrete tomography can be solved in polynomial time, it turns out that these window constraints cause various unexpected complexity jumps back and forth from polynomialtime solvability to NP-hardness.",

author = "Andreas Alpers and Peter Gritzmann",

note = "Funding Information: ∗The authors gratefully acknowledge support through the German Research Foundation Grant GR 993/10-2 and the European COST Network MP1207. †Address for correspondence: Zentrum Mathematik, Technische Universit{\"a}t M{\"u}nchen, D-85747 Garching bei M{\"u}nchen, Germany",

year = "2017",

doi = "10.3233/FI-2017-1588",

language = "English",

volume = "155",

pages = "321--340",

journal = "Fundamenta Informaticae",

issn = "0169-2968",

publisher = "SAGE Publications Ltd",

number = "4",

}

TY - JOUR

T1 - Reconstructing Binary Matrices underWindow Constraints from their Row and Column Sums

AU - Alpers, Andreas

AU - Gritzmann, Peter

N1 - Funding Information: ∗The authors gratefully acknowledge support through the German Research Foundation Grant GR 993/10-2 and the European COST Network MP1207. †Address for correspondence: Zentrum Mathematik, Technische Universität München, D-85747 Garching bei München, Germany

PY - 2017

Y1 - 2017

N2 - The present paper deals with the discrete inverse problem of reconstructing binary matrices from their row and column sums under additional constraints on the number and pattern of entries in specified minors. While the classical consistency and reconstruction problems for two directions in discrete tomography can be solved in polynomial time, it turns out that these window constraints cause various unexpected complexity jumps back and forth from polynomialtime solvability to NP-hardness.

AB - The present paper deals with the discrete inverse problem of reconstructing binary matrices from their row and column sums under additional constraints on the number and pattern of entries in specified minors. While the classical consistency and reconstruction problems for two directions in discrete tomography can be solved in polynomial time, it turns out that these window constraints cause various unexpected complexity jumps back and forth from polynomialtime solvability to NP-hardness.

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

U2 - 10.3233/FI-2017-1588

DO - 10.3233/FI-2017-1588

M3 - Article

AN - SCOPUS:85029529322

SN - 0169-2968

VL - 155

SP - 321

EP - 340

JO - Fundamenta Informaticae

JF - Fundamenta Informaticae

IS - 4

ER -

Reconstructing Binary Matrices underWindow Constraints from their Row and Column Sums

Abstract

Access to Document

Other files and links

Fingerprint

Cite this