Alpers, Andreas 
ORCID: 0000-0003-0663-6037 and Gritzmann, Peter
(2017)
Reconstructing Binary Matrices underWindow Constraints from their Row and Column Sums.
FUNDAMENTA INFORMATICAE, 155 (4).
pp. 321-340.
ISSN 0169-2968, 1875-8681
|
Text
1702.06121v1.pdf - Author Accepted Manuscript Download (635kB) | Preview |
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 $\mathbb{N}\mathbb{P}$-hardness.
| Item Type: | Article |
|---|---|
| Uncontrolled Keywords: | Tomography, analytical reconstruction algorithms, consistency conditions |
| Depositing User: | Symplectic Admin |
| Date Deposited: | 05 May 2020 10:24 |
| Last Modified: | 04 Jul 2025 19:54 |
| DOI: | 10.3233/FI-2017-1588 |
| Related Websites: | |
| URI: | https://livrepository.liverpool.ac.uk/id/eprint/3085597 |
Altmetric
Altmetric