SwePub
Sök i LIBRIS databas

  Utökad sökning

onr:"swepub:oai:DiVA.org:liu-133774"
 

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
  • Konferensbidrag (refereegranskat)
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

Kungliga biblioteket hanterar dina personuppgifter i enlighet med EU:s dataskyddsförordning (2018), GDPR. Läs mer om hur det funkar här.
Så här hanterar KB dina uppgifter vid användning av denna tjänst.

 
pil uppåt Stäng

Kopiera och spara länken för att återkomma till aktuell vy