Path Puzzles: Discrete Tomography with a Path Constraint is Hard
| Autor: | Jeffrey Bosboom, Erik D. Demaine, Justin Kopinsky, Adam Hesterberg, Roderick Kimball, Martin L. Demaine |
|---|---|
| Rok vydání: | 2019 |
| Předmět: |
Computational Geometry (cs.CG)
FOS: Computer and information sciences Combinatorics Constraint (information theory) Matching (graph theory) Path (graph theory) Computer Science - Computational Geometry Discrete Mathematics and Combinatorics Column (database) Discrete tomography Theoretical Computer Science Mathematics |
| Zdroj: | Springer Japan |
| ISSN: | 1435-5914 0911-0119 |
| DOI: | 10.1007/s00373-019-02092-5 |
| Popis: | We prove that path puzzles with complete row and column information--or equivalently, 2D orthogonal discrete tomography with Hamiltonicity constraint--are strongly NP-complete, ASP-complete, and #P-complete. Along the way, we newly establish ASP-completeness and #P-completeness for 3-Dimensional Matching and Numerical 3-Dimensional Matching. Comment: 16 pages, 8 figures. Revised proof of Theorem 2.4. 2-page abstract appeared in Abstracts from the 20th Japan Conference on Discrete and Computational Geometry, Graphs, and Games (JCDCGGG 2017) |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full text from SpringerLink