Reconstructing 3-colored grids from horizontal and vertical projections is NP-hard: A solution to the 2-atom problem in discrete tomography
From MaRDI portal
(Redirected from Publication:2902905)
Combinatorial aspects of tessellation and tiling problems (05B45) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Combinatorial complexity of geometric structures (52C45) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Recommendations
- Reconstructing 3-Colored Grids from Horizontal and Vertical Projections Is NP-hard
- Realizing disjoint degree sequences of span at most two: a tractable discrete tomography problem
- Solving some instances of the 2-color problem
- A reconstruction algorithm for a subclass of instances of the 2-color problem
- Tile-packing tomography is \(\mathbb{NP}\)-hard
Cited in
(20)- Navigating between packings of graphic sequences
- On polyatomic tomography over abelian groups: some remarks on consistency, tree packings and complexity
- Path puzzles: discrete tomography with a path constraint is hard
- Half-regular factorizations of the complete bipartite graph
- A formulation of the wide partition conjecture using the atom problem in discrete tomography
- Reconstruction of convex polyominoes with a blocking component
- Constructing bounded degree graphs with prescribed degree and neighbor degree sequences
- 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
- Reconstructing 3-Colored Grids from Horizontal and Vertical Projections Is NP-hard
- Solving some instances of the 2-color problem
- On double-resolution imaging and discrete tomography
- Highly complex 4-colored rectangle-free grids -- solution unsolved multiple-valued problems
- A note on packing of graphic \(n\)-tuples
- 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
- Reconstructing polyatomic structures from discrete X-rays: NP-completeness proof for three atoms
- Sequential stub matching for asymptotically uniform generation of directed graphs with a given degree sequence
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
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2902905)
