Show simple item record

dc.rights.licenseCC-BY-NC-ND
dc.contributor.advisorWoeginger, G.J.
dc.contributor.advisorHurkens, C.A.J.
dc.contributor.advisorHoogeveen, J.A.
dc.contributor.authorBodlaender, M.H.L.
dc.date.accessioned2018-07-19T17:04:31Z
dc.date.available2018-07-19T17:04:31Z
dc.identifier.urihttps://studenttheses.uu.nl/handle/20.500.12932/29557
dc.description.abstractWe 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.
dc.description.sponsorshipUtrecht University
dc.format.extent266534
dc.format.mimetypeapplication/pdf
dc.language.isoen
dc.titleCinderella and the Bucketgame
dc.type.contentMaster Thesis
dc.rights.accessrightsOpen Access
dc.subject.keywordsGraph theory, combinatorial game, on-line algorithms, perfect graphs
dc.subject.courseuuApplied Computing Science


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record