Search: onr:"swepub:oai:DiVA.org:liu-133774" >
Single-Player and T...
Single-Player and Two-Player Buttons & Scissors Games
-
- Burke, Kyle (author)
- Plymouth State University, NH, USA
-
- Demaine, Erik D. (author)
- Massachusetts Institute of Technology, MA, USA
-
- Gregg, Harrison (author)
- Bard Coll Simons Rock, MA, USA
-
show more...
-
- Hearn, Robert A. (author)
- Portola Valley, CA USA
-
- Hesterberg, Adam (author)
- Massachusetts Institute of Technology, MA, USA
-
- Hoffmann, Michael (author)
- Swiss Federal Institute Technology, Switzerland
-
- Ito, Hiro (author)
- The University of Electro-Communications, Chofu, Japan
-
- Kostitsyna, Irina (author)
- University of Iibre Bruxelles, Belgium
-
- Leonard, Jody (author)
- Bard Coll Simons Rock, MA, USA
-
- Loeffler, Maarten (author)
- University of Utrecht, Netherlands
-
- Santiago, Aaron (author)
- Bard Coll Simons Rock, MA, USA
-
- Schmidt, Christiane (author)
- Linköpings universitet,Kommunikations- och transportsystem,Tekniska fakulteten,University of Elect Communicat, Japan
-
- Uehara, Ryuhei (author)
- Japan Adv Institute Science and Technology, Japan
-
- Uno, Yushi (author)
- Osaka Prefecture University, Japan
-
- Williams, Aaron (author)
- Bard Coll Simons Rock, MA, USA
-
show less...
-
(creator_code:org_t)
- 2016-11-24
- 2016
- English.
-
In: DISCRETE AND COMPUTATIONAL GEOMETRY AND GRAPHS, JCDCGG 2015. - Cham : SPRINGER INT PUBLISHING AG. - 9783319485324 - 9783319485317 ; , s. 60-72
- Related links:
-
http://arxiv.org/pdf...
-
show more...
-
https://urn.kb.se/re...
-
https://doi.org/10.1...
-
show less...
Abstract
Subject headings
Close
- We study the computational complexity of the Buttons amp; 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 amp;lt;= 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 are PSPACE-complete.
Subject headings
- NATURVETENSKAP -- Matematik -- Diskret matematik (hsv//swe)
- NATURAL SCIENCES -- Mathematics -- Discrete Mathematics (hsv//eng)
Publication and Content Type
- ref (subject category)
- kon (subject category)
Find in a library
To the university's database
- By the author/editor
-
Burke, Kyle
-
Demaine, Erik D.
-
Gregg, Harrison
-
Hearn, Robert A.
-
Hesterberg, Adam
-
Hoffmann, Michae ...
-
show more...
-
Ito, Hiro
-
Kostitsyna, Irin ...
-
Leonard, Jody
-
Loeffler, Maarte ...
-
Santiago, Aaron
-
Schmidt, Christi ...
-
Uehara, Ryuhei
-
Uno, Yushi
-
Williams, Aaron
-
show less...
- About the subject
-
- NATURAL SCIENCES
-
NATURAL SCIENCES
-
and Mathematics
-
and Discrete Mathema ...
- Articles in the publication
-
DISCRETE AND COM ...
- By the university
-
Linköping University