Computational complexity of three-dimensional discrete tomography with missing data

DOI10.1007/S13160-021-00464-0MaRDI QIDQ2231602zbMATH OpenOpenAlexFDO

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

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)

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

Cites work

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

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
• scientific article; zbMATH DE number 2165135 (Why is no real title available?)

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)