Reconstructing 3-Colored Grids from Horizontal and Vertical Projections is NP-Hard: A Solution to the 2-Atom Problem in Discrete Tomography

DOI10.1137/100799733zbMath1244.68035OpenAlexW2110107802MaRDI QIDQ2902905

Martin Matamala, Flavio Guíñez, Christoph Dürr

Publication date: 22 August 2012

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/100799733

zbMATH Keywords

tiling NP-complete discrete tomography 2-atom problem

Mathematics Subject Classification ID

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) Combinatorial aspects of tessellation and tiling problems (05B45) Combinatorial complexity of geometric structures (52C45)

Related Items (14)

Reconstruction of convex polyominoes with a blocking component ⋮ Colour degree matrices of graphs with at most one cycle ⋮ Extremal Theorems for Degree Sequence Packing and the Two-Color Discrete Tomography Problem ⋮ Reconstructing binary matrices with timetabling constraints ⋮ Half-regular factorizations of the complete bipartite graph ⋮ On Double-Resolution Imaging and Discrete Tomography ⋮ On polyatomic tomography over abelian groups: some remarks on consistency, tree packings and complexity ⋮ Constructing bounded degree graphs with prescribed degree and neighbor degree sequences ⋮ A formulation of the wide partition conjecture using the atom problem in discrete tomography ⋮ A note on packing of graphic \(n\)-tuples ⋮ Navigating between packings of graphic sequences ⋮ Supermodularity in Unweighted Graph Optimization I: Branchings and Matchings ⋮ Supermodularity in Unweighted Graph Optimization III: Highly Connected Digraphs ⋮ On the Degree Sequence of 3-Uniform Hypergraph: A New Sufficient Condition

This page was built for publication: Reconstructing 3-Colored Grids from Horizontal and Vertical Projections is NP-Hard: A Solution to the 2-Atom Problem in Discrete Tomography