On polyatomic tomography over abelian groups: some remarks on consistency, tree packings and complexity
Publication:2197684
DOI10.1007/S00454-020-00180-5zbMath1453.68114OpenAlexW3004050198MaRDI QIDQ2197684
Barbara Langfeld, Peter Gritzmann
Publication date: 1 September 2020
Published in: Discrete \& Computational Geometry (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00454-020-00180-5
NP-completenesspolynomial-time algorithmdiscrete tomographydiscrete inverse problempolyatomic tomography
Analysis of algorithms and problem complexity (68Q25) Combinatorics in computer science (68R05) Matrices over special rings (quaternions, finite fields, etc.) (15B33) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Cites Work
- Unnamed Item
- Unnamed Item
- On the reconstruction of binary and permutation matrices under (binary) tomographic constraints
- Matrices of zeros and ones with fixed row and column sum vectors
- On the computational complexity of reconstructing lattice sets from their \(X\)-rays
- On the computational complexity of determining polyatomic structures by X-rays
- Discrete tomography. Foundations, algorithms, and applications
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- A result on graph-coloring
- Enumeration of matrices with prescribed row and column sums
- Combinatorial Optimization
- Reconstructing 3-Colored Grids from Horizontal and Vertical Projections is NP-Hard: A Solution to the 2-Atom Problem in Discrete Tomography
- On the Problem of Decomposing a Graph into n Connected Factors
- Matrices of zeros and ones
- Edge-Disjoint Spanning Trees of Finite Graphs
- 13. On the reconstruction of static and dynamic discrete structures
- Reducibility among Combinatorial Problems
- Discrete Tomography of Model Sets: Reconstruction and Uniqueness
- On the spanning tree packing number of a graph: A survey
This page was built for publication: On polyatomic tomography over abelian groups: some remarks on consistency, tree packings and complexity
