Reconstructing polyatomic structures from discrete X-rays: NP-completeness proof for three atoms

DOI10.1016/S0304-3975(99)00325-4MaRDI QIDQ5941271zbMATH OpenFDO

Authors Marek Chrobak, Christoph Dürr

Publication date 20 August 2001

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/S0304-3975(99)00325-4

zbMATH Keywords

discrete tomographyhigh-resolution transmission electron microscopemulti-commodity max flow

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Biomedical imaging and signal processing (92C55)

Recommendations

• On the computational complexity of determining polyatomic structures by X-rays
• scientific article; zbMATH DE number 1594509
• Reconstructing 3-colored grids from horizontal and vertical projections is NP-hard: A solution to the 2-atom problem in discrete tomography
• On the computational complexity of reconstructing lattice sets from their X-rays
• Solving multicolor discrete tomography problems by using prior knowledge

Cites work

• scientific article; zbMATH DE number 3182201 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Matrices of zeros and ones with fixed row and column sum vectors
• On the Complexity of Timetable and Multicommodity Flow Problems
• On the computational complexity of determining polyatomic structures by X-rays
• On the computational complexity of reconstructing lattice sets from their X-rays
• The reconstruction of binary patterns from their projections
• Three-dimensional Statistical Data Security Problems

Cited in

(22)

• On the computational complexity of reconstructing lattice sets from their X-rays
• Tiling with bars under tomographic constraints.
• On tiling under tomographic constraints.
• On the computational complexity of determining polyatomic structures by X-rays
• On polyatomic tomography over abelian groups: some remarks on consistency, tree packings and complexity
• A formulation of the wide partition conjecture using the atom problem in discrete tomography
• A solvable case of image reconstruction in discrete tomography
• Using graphs for some discrete tomography problems
• scientific article; zbMATH DE number 1594509 (Why is no real title available?)
• Solving the two color problem: an heuristic algorithm
• Approximating Bicolored Images from Discrete Projections
• Reconstruction of binary matrices under adjacency constraints
• Solving some instances of the 2-color problem
• On the use of graphs in discrete tomography
• On the use of graphs in discrete tomography
• Reconstruction of domino tiling from its two orthogonal projections
• The NP-completeness of a tomographical problem on bicolored domino tilings
• Realizing disjoint degree sequences of span at most two: a tractable discrete tomography problem
• A reconstruction algorithm for a subclass of instances of the 2-color problem
• Minimal multicut and maximal integer multiflow: a survey
• Reconstruction of binary matrices under fixed size neighborhood constraints
• Reconstructing \(hv\)-convex multi-coloured polyominoes

This page was built for publication: Reconstructing polyatomic structures from discrete X-rays: NP-completeness proof for three atoms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5941271)