A reconstruction algorithm for a subclass of instances of the 2-color problem

DOI10.1016/j.tcs.2010.08.004zbMath1234.68440OpenAlexW2047229977MaRDI QIDQ638558

Simone Rinaldi, Stefano Brocchi, Andrea Frosini

Publication date: 12 September 2011

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

Full work available at URL: https://doi.org/10.1016/j.tcs.2010.08.004

zbMATH Keywords

polynomial time algorithmdiscrete tomography\(c\)-color problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Biomedical imaging and signal processing (92C55) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Related Items (3)

New sufficient conditions on the degree sequences of uniform hypergraphs ⋮ A formulation of the wide partition conjecture using the atom problem in discrete tomography ⋮ On the Degree Sequence of 3-Uniform Hypergraph: A New Sufficient Condition

Cites Work

• Reconstruction of binary matrices under fixed size neighborhood constraints
• On the computational complexity of reconstructing lattice sets from their \(X\)-rays
• On the computational complexity of determining polyatomic structures by X-rays
• A solvable case of image reconstruction in discrete tomography
• Using graphs for some discrete tomography problems
• Combinatorial Properties of Matrices of Zeros and Ones
• Reconstructing 3-Colored Grids from Horizontal and Vertical Projections Is NP-hard
• On the use of graphs in discrete tomography
• Reconstructing polyatomic structures from discrete X-rays: NP-completeness proof for three atoms

This page was built for publication: A reconstruction algorithm for a subclass of instances of the 2-color problem