15 citations · 33 across the 4 of their papers we have counts for
5 papers
Who Needs Crossings?: Noncrossing Linkages are Universal, and Deciding (Global) Rigidity is Hard
Zachary Abel, Erik D. Demaine, Martin L. Demaine +3
We exactly settle the complexity of graph realization, graph rigidity, and graph global rigidity as applied to three types of graphs: "globally noncrossing" graphs, which avoid cro…
Solving the Rubik's Cube Optimally is NP-complete
Erik D. Demaine, Sarah Eisenstat, Mikhail Rudoy
In this paper, we prove that optimally solving an Rubik's Cube is NP-complete by reducing from the Hamiltonian Cycle problem in square grid graphs. This impro…
Two Hands Are Better Than One (up to constant factors)
Sarah Cannon, Erik D. Demaine, Martin L. Demaine +5
We study the difference between the standard seeded model of tile self-assembly, and the "seedless" two-handed model of tile self-assembly. Most of our results suggest that the two…
Algorithms for Solving Rubik's Cubes
Erik D. Demaine, Martin L. Demaine, Sarah Eisenstat +2
The Rubik's Cube is perhaps the world's most famous and iconic puzzle, well-known to have a rich underlying mathematical structure (group theory). In this paper, we show that the R…
Remarks on separating words
Erik D. Demaine, Sarah Eisenstat, Jeffrey Shallit +1
The separating words problem asks for the size of the smallest DFA needed to distinguish between two words of length <= n (by accepting one and rejecting the other). In this paper…