Show simple item record

dc.rights.licenseCC-BY-NC-ND
dc.contributor.advisorBodlaender, H.L.
dc.contributor.authorPrins, S.J.
dc.date.accessioned2015-08-17T17:00:33Z
dc.date.available2015-08-17T17:00:33Z
dc.date.issued2015
dc.identifier.urihttps://studenttheses.uu.nl/handle/20.500.12932/21067
dc.description.abstractKayles is a two player game played on a graph. The game can be defined as follows: both players take turns picking a node from a graph G. They remove that node and all its neighbors. When there are no more nodes left, the player whose turn it is loses. An alternate but equivalent way of phrasing it is to say that both players take turns picking an unmarked node from graph G and marking it and its neighbors. When all nodes are marked, the player whose turn it is loses. In this paper a variation of the game Kayles is studied, where instead of removing or marking just the neighbors of the chosen node, the players remove or mark the nodes at a certain distance d. Note that in this variation there is a difference between marking and removing a node. When the players remove nodes, the distance between other nodes can change, but when the players mark nodes the distances stay the same. This paper proves that Kayles with marking is PSPACE complete and that Kayles with removing is PSPACE complete for distance two. Furthermore an exact algorithm for finding a winning strategy for Kayles with marking is given for distance two. It is also shown that both versions of Kayles can be solved in polynomial time on certain classes of graphs.
dc.description.sponsorshipUtrecht University
dc.format.extent361085
dc.format.mimetypeapplication/pdf
dc.language.isoen_US
dc.titleFinding a winning strategy in variations of Kayles
dc.type.contentMaster Thesis
dc.rights.accessrightsOpen Access
dc.subject.keywordsKayles; PSPACE; exact; game
dc.subject.courseuuComputing Science


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record