Tile-packing tomography is NP-hard

DOI10.1007/S00453-011-9498-1MaRDI QIDQ1759658zbMATH OpenOpenAlexFDO

Authors Marek Chrobak, Christoph Dürr, Flavio Guiñez, Antoni Lozano, Nguyen Kim Thang

Publication date 21 November 2012

Published in Algorithmica (Search for Journal in Brave)

Copyright license Creative Commons Attribution-NonCommercial 4.0 International

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

zbMATH Keywords

\(\mathbb{NP}\)-hardnessaffine independencediscrete tomographytilings

Mathematics Subject Classification ID

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

Recommendations

• Tile-packing tomography is \({\mathbb{NP}}\)-hard
• On tiling under tomographic constraints.
• The NP-completeness of a tomographical problem on bicolored domino tilings
• scientific article; zbMATH DE number 2087458
• Reconstruction of domino tiling from its two orthogonal projections

Cites work

• 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.
• Discrete tomography. Foundations, algorithms, and applications
• Matrices of zeros and ones
• On the computational complexity of determining polyatomic structures by X-rays
• On tiling under tomographic constraints.
• Reconstructing 3-Colored Grids from Horizontal and Vertical Projections Is NP-hard
• Reconstruction of binary matrices under adjacency constraints
• Reconstruction of domino tiling from its two orthogonal projections
• The reconstruction of a subclass of domino tilings from two projections
• Tiling with bars under tomographic constraints.

Cited in

(7)

• On tiling under tomographic constraints.
• Path puzzles: discrete tomography with a path constraint is hard
• Reconstructing 3-colored grids from horizontal and vertical projections is NP-hard: A solution to the 2-atom problem in discrete tomography
• Tile-packing tomography is \({\mathbb{NP}}\)-hard
• Reconstructing 3-Colored Grids from Horizontal and Vertical Projections Is NP-hard
• About the Complexity of Timetables and 3-Dimensional Discrete Tomography: A Short Proof of NP-Hardness
• The NP-completeness of a tomographical problem on bicolored domino tilings

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

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