26 citations · 54 across the 9 of their papers we have counts for
6 papers · 1 filter
Open Problems from CCCG 2002
Erik D. Demaine, Joseph O'Rourke
A list of the problems presented on August 12, 2002 at the open-problem session of the 14th Canadian Conference on Computational Geometry held in Lethbridge, Alberta, Canada.
Efficient Tree Layout in a Multilevel Memory Hierarchy
Stephen Alstrup, Michael A. Bender, Erik D. Demaine +3
We consider the problem of laying out a tree with fixed parent/child structure in hierarchical memory. The goal is to minimize the expected number of block transfers performed duri…
Tetris is Hard, Even to Approximate
Erik D. Demaine, Susan Hohenberger, David Liben-Nowell
In the popular computer game of Tetris, the player is given a sequence of tetromino pieces and must pack them into a rectangular gameboard initially occupied by a given configurati…
PSPACE-Completeness of Sliding-Block Puzzles and Other Problems through the Nondeterministic Constraint Logic Model of Computation
Robert A. Hearn, Erik D. Demaine
We present a nondeterministic model of computation based on reversing edge directions in weighted directed graphs with minimum in-flow constraints on vertices. Deciding whether thi…
Coin-Moving Puzzles
Erik D. Demaine, Martin L. Demaine, Helena A. Verrill
We introduce a new family of one-player games, involving the movement of coins from one configuration to another. Moves are restricted so that a coin can be placed only in a positi…
Long Proteins with Unique Optimal Foldings in the H-P Model
Oswin Aichholzer, David Bremner, Erik D. Demaine +3
It is widely accepted that (1) the natural or folded state of proteins is a global energy minimum, and (2) in most cases proteins fold to a unique state determined by their amino a…