Paper by Erik D. Demaine
- Kyle Burke, Erik Demaine, Robert Hearn, Adam Hesterberg, Michael Hoffmann, Hiro Ito, Irina Kostitsyna, Maarten Löffler, Yushi Uno, Christiane Schmidt, Ryuhei Uehara, and Aaron Williams, “Single-player and two-player Buttons & Scissors games”, in Revised Papers from the 18th Japan Conference on Discrete and Computational Geometry and Graphs (JCDCGG 2015), Lecture Notes in Computer Science, volume 9943, Kyoto, Japan, September 14–16, 2015, pages 60–72.
We study the computational complexity of the Buttons & Scissors game and
obtain sharp thresholds with respect to several parameters. Specifically we
show that the game is NP-complete for C = 2 colors but
polytime solvable for C = 1. Similarly the game is
NP-complete if every color is used by at most F = 4 buttons
but polytime solvable for F ≤ 3. We also consider
restrictions on the board size, cut directions, and cut sizes. Finally, we
introduce several natural two-player versions of the game and show that they
- This paper is also available from SpringerLink.
- The paper is available in PDF (4478k).
- See information on file formats.
- [Google Scholar search]
- Related papers:
- Buttons_JCDCGG2015 (Single-player and two-player Buttons & Scissors games)
See also other papers by Erik Demaine.
These pages are generated automagically from a
Last updated July 7, 2020 by