1 citations · 2 across the 7 of their papers we have counts for
Showing cs.CCShow all
3 papers · 1 filter
cs.CC2015
Bust-a-Move/Puzzle Bobble is NP-Complete
Erik D. Demaine, Stefan Langerman
We prove that the classic 1994 Taito video game, known as Puzzle Bobble or Bust-a-Move, is NP-complete. Our proof applies to the perfect-information version where the bubble sequen…
cs.CC2014
Zig-Zag Numberlink is NP-Complete
Aaron Adcock, Erik D. Demaine, Martin L. Demaine +4
When can terminal pairs in an grid be connected by vertex-disjoint paths that cover all vertices of the grid? We prove that this problem is NP-complete. Our ha…
cs.CC2010
Self-Assembly of Arbitrary Shapes Using RNAse Enzymes: Meeting the Kolmogorov Bound with Small Scale Factor (extended abstract)
Erik D. Demaine, Matthew J. Patitz, Robert T. Schweller +1
We consider a model of algorithmic self-assembly of geometric shapes out of square Wang tiles studied in SODA 2010, in which there are two types of tiles (e.g., constructed out of…