On polyatomic tomography over abelian groups: some remarks on consistency, tree packings and complexity

DOI10.1007/S00454-020-00180-5MaRDI QIDQ2197684zbMATH OpenOpenAlexFDO

Authors Peter Gritzmann, Barbara Langfeld

Publication date 1 September 2020

Published in Discrete \& Computational Geometry (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1007/s00454-020-00180-5

zbMATH Keywords

NP-completenessdiscrete tomographypolynomial-time algorithmdiscrete inverse problempolyatomic tomography

Mathematics Subject Classification ID

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)

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

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 863488 (Why is no real title available?)
• A result on graph-coloring
• Combinatorial optimization. Packing and covering
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Discrete tomography of model sets: reconstruction and uniqueness
• Discrete tomography. Foundations, algorithms, and applications
• Edge-Disjoint Spanning Trees of Finite Graphs
• Enumeration of matrices with prescribed row and column sums
• Matrices of zeros and ones
• Matrices of zeros and ones with fixed row and column sum vectors
• On the Problem of Decomposing a Graph into n Connected Factors
• On the computational complexity of determining polyatomic structures by X-rays
• On the computational complexity of reconstructing lattice sets from their \(X\)-rays
• On the reconstruction of binary and permutation matrices under (binary) tomographic constraints
• On the reconstruction of static and dynamic discrete structures
• On the spanning tree packing number of a graph: A survey
• Reconstructing 3-colored grids from horizontal and vertical projections is NP-hard: A solution to the 2-atom problem in discrete tomography
• Reducibility among combinatorial problems

Cited in

(1)

• Theory Is Forever

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)