Name
Abstract | ||
|---|---|---|
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. |
Year | DOI | Venue |
|---|---|---|
2020 | 10.1007/s00373-019-02092-5 | Graphs and Combinatorics |
Keywords | DocType | Volume |
Discrete tomography, ASP-completeness, #P-completeness, 3-Dimensional Matching
, Numerical 3-Dimensional Matching
| Journal | 36 |
Issue | ISSN | Citations |
2 | 0911-0119 | 0 |
PageRank | References | Authors |
0.34 | 0 | 6 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Jeffrey Bosboom | 1 | 117 | 7.70 |
| Erik D. Demaine | 2 | 4624 | 388.59 |
| Martin L. Demaine | 3 | 592 | 84.37 |
| Adam Hesterberg | 4 | 0 | 1.01 |
| Roderick Kimball | 5 | 0 | 0.34 |
| Justin Kopinsky | 6 | 39 | 5.23 |