On polyatomic tomography over abelian groups: some remarks on consistency, tree packings and complexity
DOI10.1007/S00454-020-00180-5zbMATH Open1453.68114OpenAlexW3004050198MaRDI QIDQ2197684FDOQ2197684
Authors: Peter Gritzmann, Barbara Langfeld 
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
Recommendations
- Reconstructing binary matrices under window constraints from their row and column sums
- Reconstructing polyatomic structures from discrete X-rays: NP-completeness proof for three atoms
- Theory Is Forever
- scientific article; zbMATH DE number 2087481
- Matrices of zeros and ones with given line sums and a zero block
NP-completenessdiscrete tomographypolynomial-time algorithmdiscrete inverse problempolyatomic tomography
Analysis of algorithms and problem complexity (68Q25) Combinatorics in computer science (68R05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Matrices over special rings (quaternions, finite fields, etc.) (15B33) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)
Cites Work
- Title not available (Why is that?)
- Reducibility among combinatorial problems
- Discrete tomography. Foundations, algorithms, and applications
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- 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
- Edge-Disjoint Spanning Trees of Finite Graphs
- 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
- Combinatorial optimization. Packing and covering
- Matrices of zeros and ones
- On the spanning tree packing number of a graph: A survey
- On the reconstruction of static and dynamic discrete structures
- On the computational complexity of determining polyatomic structures by X-rays
- Enumeration of matrices with prescribed row and column sums
- Title not available (Why is that?)
- A result on graph-coloring
- Discrete tomography of model sets: reconstruction and uniqueness
Cited In (1)
This page was built for publication: On polyatomic tomography over abelian groups: some remarks on consistency, tree packings and complexity
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2197684)
