Show simple item record

dc.contributor.authorBonnet, Edouard
HAL ID: 171728
ORCID: 0000-0002-1653-5822
dc.contributor.authorJamain, Florian
dc.contributor.authorSaffidine, Abdallah
dc.date.accessioned2020-09-29T15:05:18Z
dc.date.available2020-09-29T15:05:18Z
dc.date.issued2016
dc.identifier.issn0304-3975
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/21006
dc.language.isoenen
dc.subjectPSPACE
dc.subjectSlither
dc.subjectHex
dc.subjectComplexity
dc.subjectHavannah
dc.subjectTwixt
dc.subject.ddc519en
dc.titleOn the Complexity of Connection Games
dc.typeArticle accepté pour publication ou publié
dc.description.abstractenIn this paper, we study three connection games among the most widely played: havannah, twixt, and slither. We show that determining the outcome of an arbitrary input position is PSPACE-complete in all three cases. Our reductions are based on the popular graph problem generalized geography and on hex itself. We also consider the complexity of generalizations of hex parameterized by the length of the solution and establish that while short generalized hex is W[1]-hard, short hex is FPT. Finally, we prove that the ultra-weak solution to the empty starting position in hex cannot be fully adapted to any of these three games.
dc.relation.isversionofjnlnameTheoretical Computer Science
dc.relation.isversionofjnlvol644
dc.relation.isversionofjnldate2016
dc.relation.isversionofjnlpages2-28
dc.relation.isversionofdoi10.1016/j.tcs.2016.06.033
dc.identifier.urlsitehttps://hal.archives-ouvertes.fr/hal-01994450
dc.relation.isversionofjnlpublisherElsevier
dc.subject.ddclabelProbabilités et mathématiques appliquéesen
dc.relation.forthcomingnonen
dc.relation.forthcomingprintnonen
dc.description.ssrncandidatenon
dc.description.halcandidatenon
dc.description.readershiprecherche
dc.description.audienceInternational
dc.relation.Isversionofjnlpeerreviewedoui
dc.date.updated2020-09-30T10:55:41Z


Files in this item

FilesSizeFormatView

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record