View Item 
        •   Utrecht University Student Theses Repository Home
        • UU Theses Repository
        • Theses
        • View Item
        •   Utrecht University Student Theses Repository Home
        • UU Theses Repository
        • Theses
        • View Item
        JavaScript is disabled for your browser. Some features of this site may not work without it.

        Browse

        All of UU Student Theses RepositoryBy Issue DateAuthorsTitlesSubjectsThis CollectionBy Issue DateAuthorsTitlesSubjects

        Feedback Vertex Kayles Finding a wining strategy in a two-player combinatorial game

        Thumbnail
        View/Open
        Feedback Vertex Kayles.pdf (519.7Kb)
        Publication date
        2016
        Author
        Vries, G.J. de
        Metadata
        Show full item record
        Summary
        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.
        URI
        https://studenttheses.uu.nl/handle/20.500.12932/23662
        Collections
        • Theses
        Utrecht university logo