Computational complexity of three-dimensional discrete tomography with missing data

DOI10.1007/S13160-021-00464-0zbMATH Open1473.90008OpenAlexW3140030971MaRDI QIDQ2231602FDOQ2231602

Authors: Kei Kimura, Takuya Kamehashi 

Publication date: 30 September 2021

Published in: Japan Journal of Industrial and Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s13160-021-00464-0

Recommendations

• On the computational complexity of reconstructing three-dimensional lattice sets from their two-dimensional \(X\)-rays
• The reconstruction of some 3D convex polyominoes from orthogonal projections
• scientific article; zbMATH DE number 2165135
• On the computational complexity of reconstructing lattice sets from their \(X\)-rays
• Uniqueness in discrete tomography: Three remarks and a corollary

zbMATH Keywords

computational complexitycontingency tablesdiscrete tomographyinteger linear programming formulation

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Research exposition (monographs, survey articles) pertaining to operations research and mathematical programming (90-02) Sensitivity, stability, parametric optimization (90C31) Inventory, storage, reservoirs (90B05) Transportation, logistics and supply chain management (90B06)

Cites Work

• Discrete tomography. Foundations, algorithms, and applications
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• The Complexity of Enumeration and Reliability Problems
• The complexity of satisfiability problems
• \(N\)-fold integer programming
• Complexity of generalized satisfiability counting problems
• On the computational complexity of reconstructing lattice sets from their \(X\)-rays
• The Complexity of Three-Way Statistical Tables
• Three-dimensional Statistical Data Security Problems
• Approximating the permanent of graphs with large factors
• Perfect matching for regular graphs is \(AC^ 0\)-hard for the general matching problem
• The fewest clues problem of Picross 3D
• About the Complexity of Timetables and 3-Dimensional Discrete Tomography: A Short Proof of NP-Hardness

Cited In (3)

• Reduction from three-dimensional discrete tomography to multicommodity flow problem
• On the computational complexity of reconstructing three-dimensional lattice sets from their two-dimensional \(X\)-rays
• Title not available (Why is that?)

This page was built for publication: Computational complexity of three-dimensional discrete tomography with missing data

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