Single-player and two-player buttons & scissors games (extended abstract)

Kyle Burke; Erik D. Demaine; Harrison Gregg; Robert A. Hearn; Adam Hesterberg; Michael H.W. Hoffmann; Hiro Ito; Irina Kostitsyna; Jody Leonard; Maarten Löffler; Aaron Santiago; Christiane Schmidt; Ryuhei Uehara; Yushi Uno; Aaron Williams

doi:10.1007/978-3-319-48532-4_6

Single-player and two-player buttons & scissors games (extended abstract)

Kyle Burke
, Erik D. Demaine
, Harrison Gregg
, Robert A. Hearn
, Adam Hesterberg
, Michael H.W. Hoffmann
, Hiro Ito
, Irina Kostitsyna
, Jody Leonard
, Maarten Löffler
, Aaron Santiago
, Christiane Schmidt
, Ryuhei Uehara
, Yushi Uno
, Aaron Williams

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/Congresprocedure › Conferentiebijdrage › Academic › peer review

6 Citaten (Scopus)

159 Downloads (Pure)

Samenvatting

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 Fbackslashle 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.

Originele taal-2	Engels
Titel	Discrete and Computational Geometry and Graphs : 18th Japan Conference, JCDCGG 2015, Kyoto, Japan, September 14-16, 2015 : Revised Selected Papers
Redacteuren	Jin Akiyama, Hiro Ito, Toshinori Sakai, Yushi Uno
Plaats van productie	Dordrecht
Uitgeverij	Springer
Pagina's	60-72
Aantal pagina's	13
ISBN van elektronische versie	978-3-319-48532-4
ISBN van geprinte versie	978-3-319-48531-7
DOI's	https://doi.org/10.1007/978-3-319-48532-4_6
Status	Gepubliceerd - 2016
Extern gepubliceerd	Ja
Evenement	18th Japan Conference on Discrete and Computational Geometry and Graphs (JCDCGG 2015) - Kyoto, Japan Duur: 14 sep. 2015 → 16 sep. 2015 Congresnummer: 18

Publicatie series

Naam	Lecture Notes in Computer Science
Volume	9943

Congres

Congres	18th Japan Conference on Discrete and Computational Geometry and Graphs (JCDCGG 2015)
Verkorte titel	JCDCGG 2015
Land/Regio	Japan
Stad	Kyoto
Periode	14/09/15 → 16/09/15

Toegang tot document

10.1007/978-3-319-48532-4_6

extended-bandsFinale auteursversie , 5,55 MB

Citeer dit

Burke, K., Demaine, E. D., Gregg, H., Hearn, R. A., Hesterberg, A., Hoffmann, M. H. W., Ito, H., Kostitsyna, I., Leonard, J., Löffler, M., Santiago, A., Schmidt, C., Uehara, R., Uno, Y., & Williams, A. (2016). Single-player and two-player buttons & scissors games (extended abstract). In J. Akiyama, H. Ito, T. Sakai, & Y. Uno (editors), Discrete and Computational Geometry and Graphs : 18th Japan Conference, JCDCGG 2015, Kyoto, Japan, September 14-16, 2015 : Revised Selected Papers (blz. 60-72). (Lecture Notes in Computer Science; Vol. 9943). Springer. https://doi.org/10.1007/978-3-319-48532-4_6

Burke, Kyle ; Demaine, Erik D. ; Gregg, Harrison et al. / Single-player and two-player buttons & scissors games (extended abstract). Discrete and Computational Geometry and Graphs : 18th Japan Conference, JCDCGG 2015, Kyoto, Japan, September 14-16, 2015 : Revised Selected Papers. redacteur / Jin Akiyama ; Hiro Ito ; Toshinori Sakai ; Yushi Uno. Dordrecht : Springer, 2016. blz. 60-72 (Lecture Notes in Computer Science).

@inproceedings{e2366a940abd4fa1a551439d7589d406,

title = "Single-player and two-player buttons \& scissors games (extended abstract)",

abstract = "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 Fbackslashle 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.",

author = "Kyle Burke and Demaine, \{Erik D.\} and Harrison Gregg and Hearn, \{Robert A.\} and Adam Hesterberg and Hoffmann, \{Michael H.W.\} and Hiro Ito and Irina Kostitsyna and Jody Leonard and Maarten L{\"o}ffler and Aaron Santiago and Christiane Schmidt and Ryuhei Uehara and Yushi Uno and Aaron Williams",

year = "2016",

doi = "10.1007/978-3-319-48532-4\_6",

language = "English",

isbn = "978-3-319-48531-7",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "60--72",

editor = "Jin Akiyama and Hiro Ito and Toshinori Sakai and Yushi Uno",

booktitle = "Discrete and Computational Geometry and Graphs : 18th Japan Conference, JCDCGG 2015, Kyoto, Japan, September 14-16, 2015 : Revised Selected Papers",

address = "Germany",

note = "18th Japan Conference on Discrete and Computational Geometry and Graphs (JCDCGG 2015), JCDCGG 2015 ; Conference date: 14-09-2015 Through 16-09-2015",

}

Burke, K, Demaine, ED, Gregg, H, Hearn, RA, Hesterberg, A, Hoffmann, MHW, Ito, H, Kostitsyna, I, Leonard, J, Löffler, M, Santiago, A, Schmidt, C, Uehara, R, Uno, Y & Williams, A 2016, Single-player and two-player buttons & scissors games (extended abstract). in J Akiyama, H Ito, T Sakai & Y Uno (reds.), Discrete and Computational Geometry and Graphs : 18th Japan Conference, JCDCGG 2015, Kyoto, Japan, September 14-16, 2015 : Revised Selected Papers. Lecture Notes in Computer Science, vol. 9943, Springer, Dordrecht, blz. 60-72, 18th Japan Conference on Discrete and Computational Geometry and Graphs (JCDCGG 2015), Kyoto, Japan, 14/09/15. https://doi.org/10.1007/978-3-319-48532-4_6

Single-player and two-player buttons & scissors games (extended abstract). / Burke, Kyle; Demaine, Erik D.; Gregg, Harrison et al.
Discrete and Computational Geometry and Graphs : 18th Japan Conference, JCDCGG 2015, Kyoto, Japan, September 14-16, 2015 : Revised Selected Papers. reds. / Jin Akiyama; Hiro Ito; Toshinori Sakai; Yushi Uno. Dordrecht: Springer, 2016. blz. 60-72 (Lecture Notes in Computer Science; Vol. 9943).

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/Congresprocedure › Conferentiebijdrage › Academic › peer review

TY - GEN

T1 - Single-player and two-player buttons & scissors games (extended abstract)

AU - Burke, Kyle

AU - Demaine, Erik D.

AU - Gregg, Harrison

AU - Hearn, Robert A.

AU - Hesterberg, Adam

AU - Hoffmann, Michael H.W.

AU - Ito, Hiro

AU - Kostitsyna, Irina

AU - Leonard, Jody

AU - Löffler, Maarten

AU - Santiago, Aaron

AU - Schmidt, Christiane

AU - Uehara, Ryuhei

AU - Uno, Yushi

AU - Williams, Aaron

N1 - Conference code: 18

PY - 2016

Y1 - 2016

N2 - 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 Fbackslashle 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.

AB - 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 Fbackslashle 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.

U2 - 10.1007/978-3-319-48532-4_6

DO - 10.1007/978-3-319-48532-4_6

M3 - Conference contribution

SN - 978-3-319-48531-7

T3 - Lecture Notes in Computer Science

SP - 60

EP - 72

BT - Discrete and Computational Geometry and Graphs : 18th Japan Conference, JCDCGG 2015, Kyoto, Japan, September 14-16, 2015 : Revised Selected Papers

A2 - Akiyama, Jin

A2 - Ito, Hiro

A2 - Sakai, Toshinori

A2 - Uno, Yushi

PB - Springer

CY - Dordrecht

T2 - 18th Japan Conference on Discrete and Computational Geometry and Graphs (JCDCGG 2015)

Y2 - 14 September 2015 through 16 September 2015

ER -

Burke K, Demaine ED, Gregg H, Hearn RA, Hesterberg A, Hoffmann MHW et al. Single-player and two-player buttons & scissors games (extended abstract). In Akiyama J, Ito H, Sakai T, Uno Y, redacteurs, Discrete and Computational Geometry and Graphs : 18th Japan Conference, JCDCGG 2015, Kyoto, Japan, September 14-16, 2015 : Revised Selected Papers. Dordrecht: Springer. 2016. blz. 60-72. (Lecture Notes in Computer Science). doi: 10.1007/978-3-319-48532-4_6

Single-player and two-player buttons & scissors games (extended abstract)

Samenvatting

Publicatie series

Congres

Toegang tot document

Vingerafdruk

Citeer dit