Path puzzles: discrete tomography with a path constraint is hard

DOI10.1007/s00373-019-02092-5zbMath1433.68155arXiv1803.01176OpenAlexW2977026795WikidataQ127218018 ScholiaQ127218018MaRDI QIDQ2308497

Adam Hesterberg, Martin L. Demaine, Erik D. Demaine, Justin Kopinsky, Jeffrey Bosboom, Roderick Kimball

Publication date: 3 April 2020

Published in: Graphs and Combinatorics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1803.01176

zbMATH Keywords

discrete tomography3-dimensional matching\#P-completenessASP-completenessnumerical 3-dimensional matching

Mathematics Subject Classification ID

Computing methodologies for image processing (68U10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Cites Work

• Unnamed Item
• Unnamed Item
• Planar 3DM is NP-complete
• The Complexity of Enumeration and Reliability Problems
• The Complexity of Planar Counting Problems

This page was built for publication: Path puzzles: discrete tomography with a path constraint is hard