liu.seSök publikationer i DiVA
Ändra sökning
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf
Single-Player and Two-Player Buttons & Scissors Games
Plymouth State University, NH, USA.
MIT, MA, USA.
Bard Coll Simons Rock, MA, USA.
Portola Valley, CA USA.
Visa övriga samt affilieringar
2016 (Engelska)Ingår i: DISCRETE AND COMPUTATIONAL GEOMETRY AND GRAPHS, JCDCGG 2015 / [ed] Akiyama, J., Ito, H., Sakai, T., Uno, Y., SPRINGER INT PUBLISHING AG , 2016, Vol. 9943, s. 60-72Konferensbidrag, Publicerat paper (Refereegranskat)
Abstract [en]

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.

Ort, förlag, år, upplaga, sidor
SPRINGER INT PUBLISHING AG , 2016. Vol. 9943, s. 60-72
Serie
Lecture Notes in Computer Science, ISSN 0302-9743, E-ISSN 1611-3349
Nationell ämneskategori
Diskret matematik
Identifikatorer
URN: urn:nbn:se:liu:diva-133774DOI: 10.1007/978-3-319-48532-4_6ISI: 000389794000006ISBN: 9783319485324 (digital)ISBN: 9783319485317 (tryckt)OAI: oai:DiVA.org:liu-133774DiVA, id: diva2:1063058
Konferens
18th Japan Conference on Discrete and Computational Geometry and Graphs (JCDCG2)
Tillgänglig från: 2017-01-09 Skapad: 2017-01-09 Senast uppdaterad: 2018-02-21Bibliografiskt granskad

Open Access i DiVA

Fulltext saknas i DiVA

Övriga länkar

Förlagets fulltext

Sök vidare i DiVA

Av författaren/redaktören
Schmidt, Christiane
Av organisationen
Kommunikations- och transportsystemTekniska fakulteten
Diskret matematik

Sök vidare utanför DiVA

GoogleGoogle Scholar

doi
isbn
urn-nbn

Altmetricpoäng

doi
isbn
urn-nbn
Totalt: 159 träffar
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf