Reconstructing 3-Colored Grids from Horizontal and Vertical Projections Is NP-hard

DOI10.1007/978-3-642-04128-0_69zbMath1256.68078OpenAlexW1704269950MaRDI QIDQ3639290

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

Publication date: 29 October 2009

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-04128-0_69

Mathematics Subject Classification ID

Biomedical imaging and signal processing (92C55) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (11)

Packing of graphic n-tuples ⋮ New results on degree sequences of uniform hypergraphs ⋮ Realizing disjoint degree sequences of span at most two: a tractable discrete tomography problem ⋮ Regular switching components ⋮ A reconstruction algorithm for a subclass of instances of the 2-color problem ⋮ Solving the Two Color Problem: An Heuristic Algorithm ⋮ Approximating Bicolored Images from Discrete Projections ⋮ On the use of graphs in discrete tomography ⋮ Tile-packing tomography is \(\mathbb{NP}\)-hard ⋮ Reconstructing \(hv\)-convex multi-coloured polyominoes ⋮ Solving Some Instances of the 2-Color Problem

This page was built for publication: Reconstructing 3-Colored Grids from Horizontal and Vertical Projections Is NP-hard