Tile-packing tomography is \(\mathbb{NP}\)-hard

DOI10.1007/s00453-011-9498-1zbMath1280.68096OpenAlexW2071695456MaRDI QIDQ1759658

Marek Chrobak, Christoph Dürr, Antoni Lozano, Flavio Guíñez, Nguyen Kim Thang

Publication date: 21 November 2012

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-011-9498-1

zbMATH Keywords

tilingsdiscrete tomographyaffine independence\(\mathbb{NP}\)-hardness

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Combinatorial aspects of tessellation and tiling problems (05B45) Combinatorial aspects of packing and covering (05B40)

Cites Work

• Unnamed Item
• Tiling with bars under tomographic constraints.
• On tiling under tomographic constraints.
• On the computational complexity of determining polyatomic structures by X-rays
• Discrete tomography. Foundations, algorithms, and applications
• The reconstruction of a subclass of domino tilings from two projections
• Advances in discrete tomography and its applications. Some papers based on the presentations at the workshop on discrete tomography and its applications, New York, NY, USA, June 13--15, 2005.
• Matrices of zeros and ones
• Reconstructing 3-Colored Grids from Horizontal and Vertical Projections Is NP-hard
• Reconstruction of domino tiling from its two orthogonal projections

This page was built for publication: Tile-packing tomography is \(\mathbb{NP}\)-hard