dc.rights.license | CC-BY-NC-ND | |
dc.contributor.advisor | Bodlaender, H.L. | |
dc.contributor.advisor | Rooij, J.M.M. van | |
dc.contributor.author | Vries, G.J. de | |
dc.date.accessioned | 2016-08-22T17:01:07Z | |
dc.date.available | 2016-08-22T17:01:07Z | |
dc.date.issued | 2016 | |
dc.identifier.uri | https://studenttheses.uu.nl/handle/20.500.12932/23662 | |
dc.description.abstract | In this thesis Feedback Vertex Kayles is discused. Feedback Vertex Kayles is a two-player combinatorial game on graphs in which players remove nodes positioned on cycles. We also use the name Feedback Vertex Kayles to denote the problem of exploring whether there is a winning strategy for the first player and most often what this strategy is. This problem is an interesting and complex problem expected to be PSPACE-complete. Apart from discussing the complexity of the problem as a whole, in this thesis we will look into Feedback Vertex Kayles on specific graph classes. We discuss a number of graph classes for which we can determine in polynomial or faster time whether there is a winning strategy. To help the reader better understand the specific results and proofs and to give a deeper understanding of Feedback Vertex Kayles, this thesis first gives a broad range of important definitions and basic insights for Feedback Vertex Kayles. | |
dc.description.sponsorship | Utrecht University | |
dc.format.extent | 532190 | |
dc.format.mimetype | application/pdf | |
dc.language.iso | en | |
dc.title | Feedback Vertex Kayles
Finding a wining strategy in a two-player combinatorial game | |
dc.type.content | Master Thesis | |
dc.rights.accessrights | Open Access | |
dc.subject.keywords | Feedback, Vertex, Kayles, Feedback Vertex, Feedback Vertex Kayles, combinatorial game, game, PSPACE, PSPACE-complete, exact, graph, graphs | |
dc.subject.courseuu | Computing Science | |