25 citations · 112 across the 30 of their papers we have counts for
Showing cs.CCShow all
3 papers · 1 filter
cs.CC2020
Cyclic Shift Problems on Graphs
Kwon Kham Sai, Ryuhei Uehara, Giovanni Viglietta
We study a new reconfiguration problem inspired by classic mechanical puzzles: a colored token is placed on each vertex of a given graph; we are also given a set of distinguished c…
cs.CC2012★ 1 cited
Classic Nintendo Games are (Computationally) Hard
Greg Aloupis, Erik D. Demaine, Alan Guo +1
We prove NP-hardness results for five of Nintendo's largest video game franchises: Mario, Donkey Kong, Legend of Zelda, Metroid, and Pokemon. Our results apply to generalized versi…
cs.CC2012★ 12 cited
Gaming is a hard job, but someone has to do it!
Giovanni Viglietta
We establish some general schemes relating the computational complexity of a video game to the presence of certain common elements or mechanics, such as destroyable paths, collecti…