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

        Cinderella and the Bucketgame

        Thumbnail
        View/Open
        scriptiev1.1.pdf (260.2Kb)
        Author
        Bodlaender, M.H.L.
        Metadata
        Show full item record
        Summary
        We investigate a turn based two player game on a graph where a player (Cinderella) and an adversary (the Stepmother) empty or fill buckets. The Stepmother tries to reach an overflow by adding one liter of water to the graph every turn, after which Cinderella tries to prevent an overflow by emptying an independent set. The bucket number is the minimal bucket size needed for Cinderella to prevent an overflow and with that win the game. We looked at small graphs, holes, anti-holes and perfect graphs and determined the bucket numbers for all holes, perfect graphs, graphs with at most 6 vertices and some small anti-holes. We also investigated a greedy strategy where every turn Cinderella tries to remove as much water from the graph as possible and determined the greedy bucket numbers of most graphs that we had the regular bucket numbers of. We also prove that determining the bucket number in an offline version of the game in NP-complete.
        URI
        https://studenttheses.uu.nl/handle/20.500.12932/29557
        Collections
        • Theses
        Utrecht university logo