activity
20162022
most citedNetrunner Mate-in-1 or -2 is Weakly NP-Hard

1 citations · 1 across the 3 of their papers we have counts for

collaborators
Showing cs.CGShow all

1 paper · 1 filter

cs.CG2018

Path Puzzles: Discrete Tomography with a Path Constraint is Hard

Jeffrey Bosboom, Erik D. Demaine, Martin L. Demaine +3

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…