The NP-completeness of a tomographical problem on bicolored domino tilings

DOI10.1016/j.tcs.2004.02.004zbMath1068.05013OpenAlexW2048223006MaRDI QIDQ596077

Andrea Frosini, Giulia Simi

Publication date: 10 August 2004

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

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

zbMATH Keywords

Computational complexityDiscrete tomographyDomino tilingsReconstruction algorithm

Mathematics Subject Classification ID

Computational aspects related to convexity (52B55) Combinatorics in computer science (68R05) Biomedical imaging and signal processing (92C55) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Combinatorial aspects of tessellation and tiling problems (05B45) Tilings in (n) dimensions (aspects of discrete geometry) (52C22)

Cites Work

• Unnamed Item
• The statistics of dimers on a lattice
• Dimer problem in statistical mechanics-an exact result
• Reconstruction of domino tiling from its two orthogonal projections
• Reconstructing polyatomic structures from discrete X-rays: NP-completeness proof for three atoms