Reconstructing Binary Matrices under Window Constraints from their Row and Column Sums

Issue title: An overview of Tomography and Applications

Guest editors: Paolo Dulio, Andrea Frosini and Grzegorz Rozenberg

Article type: Research Article

Authors: Alpers, Andreas^{; †; *} | Gritzmann, Peter^{; *}

Affiliations: Zentrum Mathematik, Technische Universität München, D-85747 Garching bei München, Germany. alpers@ma.tum.de, gritzman@tum.de

Correspondence: [†] Address for correspondence: Zentrum Mathematik, Technische Universität München, D-85747 Garching bei München, Germany

Note: [*] The authors gratefully acknowledge support through the German Research Foundation Grant GR 993/10-2 and the European COST Network MP1207.

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 ℕℙ-hardness.

DOI: 10.3233/FI-2017-1588

Journal: Fundamenta Informaticae, vol. 155, no. 4, pp. 321-340, 2017