Sökning: onr:"swepub:oai:DiVA.org:liu-133774" >
Single-Player and T...
Single-Player and Two-Player Buttons & Scissors Games
-
- Burke, Kyle (författare)
- Plymouth State University, NH, USA
-
- Demaine, Erik D. (författare)
- Massachusetts Institute of Technology, MA, USA
-
- Gregg, Harrison (författare)
- Bard Coll Simons Rock, MA, USA
-
visa fler...
-
- Hearn, Robert A. (författare)
- Portola Valley, CA USA
-
- Hesterberg, Adam (författare)
- Massachusetts Institute of Technology, MA, USA
-
- Hoffmann, Michael (författare)
- Swiss Federal Institute Technology, Switzerland
-
- Ito, Hiro (författare)
- The University of Electro-Communications, Chofu, Japan
-
- Kostitsyna, Irina (författare)
- University of Iibre Bruxelles, Belgium
-
- Leonard, Jody (författare)
- Bard Coll Simons Rock, MA, USA
-
- Loeffler, Maarten (författare)
- University of Utrecht, Netherlands
-
- Santiago, Aaron (författare)
- Bard Coll Simons Rock, MA, USA
-
- Schmidt, Christiane (författare)
- Linköpings universitet,Kommunikations- och transportsystem,Tekniska fakulteten,University of Elect Communicat, Japan
-
- Uehara, Ryuhei (författare)
- Japan Adv Institute Science and Technology, Japan
-
- Uno, Yushi (författare)
- Osaka Prefecture University, Japan
-
- Williams, Aaron (författare)
- Bard Coll Simons Rock, MA, USA
-
visa färre...
-
(creator_code:org_t)
- 2016-11-24
- 2016
- Engelska.
-
Ingår i: DISCRETE AND COMPUTATIONAL GEOMETRY AND GRAPHS, JCDCGG 2015. - Cham : SPRINGER INT PUBLISHING AG. - 9783319485324 - 9783319485317 ; , s. 60-72
- Relaterad länk:
-
http://arxiv.org/pdf...
-
visa fler...
-
https://urn.kb.se/re...
-
https://doi.org/10.1...
-
visa färre...
Abstract
Ämnesord
Stäng
- 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.
Ämnesord
- NATURVETENSKAP -- Matematik -- Diskret matematik (hsv//swe)
- NATURAL SCIENCES -- Mathematics -- Discrete Mathematics (hsv//eng)
Publikations- och innehållstyp
- ref (ämneskategori)
- kon (ämneskategori)
Hitta via bibliotek
Till lärosätets databas
- Av författaren/redakt...
-
Burke, Kyle
-
Demaine, Erik D.
-
Gregg, Harrison
-
Hearn, Robert A.
-
Hesterberg, Adam
-
Hoffmann, Michae ...
-
visa fler...
-
Ito, Hiro
-
Kostitsyna, Irin ...
-
Leonard, Jody
-
Loeffler, Maarte ...
-
Santiago, Aaron
-
Schmidt, Christi ...
-
Uehara, Ryuhei
-
Uno, Yushi
-
Williams, Aaron
-
visa färre...
- Om ämnet
-
- NATURVETENSKAP
-
NATURVETENSKAP
-
och Matematik
-
och Diskret matemati ...
- Artiklar i publikationen
-
DISCRETE AND COM ...
- Av lärosätet
-
Linköpings universitet