Login
- Titel:
Reconstructing binary matrices under window constraints from their row and column sums
- Dokumenttyp:
- Zeitschriftenaufsatz
- Autor(en):
- Alpers, A. and P. Gritzmann
- 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 polynomial-time solvability to NP-hardness.
- Zeitschriftentitel:
- Fundamenta Informaticae
- Jahr:
- 2017
- Heft / Issue:
- 153
- Seitenangaben Beitrag:
- 1-20
- Reviewed:
- ja
- Sprache:
- en
- Volltext / DOI:
- doi:10.3233/FI-2017-1588
- TUM Einrichtung:
- Lehrstuhl für Angewandte Geometrie und Diskrete Mathematik
BibTeX
Vorkommen:
- mediaTUM GesamtbestandEinrichtungenSchools TUM School of Computation, Information and TechnologyDepartmentsMathematicsLehrstuhl für Angewandte Geometrie und Diskrete Mathematik (N.N.)PublikationenGritzmann, Peter