The Cinderella game on holes and anti-holes

M.H.L. Bodlaender, C.A.J. Hurkens, G.J. Woeginger

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

5 Citaten (Scopus)


We investigate a two-player game on graphs, where one player (Cinderella) wants to keep the behavior of an underlying water-bucket system stable whereas the other player (the wicked Stepmother) wants to cause overflows. The bucket number of a graph G is the smallest possible bucket size with which Cinderella can win the game. We determine the bucket numbers of all perfect graphs, and we also derive results on the bucket numbers of certain non-perfect graphs. In particular, we analyze the game on holes and (partially) on anti-holes for the cases where Cinderella sticks to a simple greedy strategy.
Originele taal-2Engels
TitelGraph-Theoretic Concepts in Computer Science (37th International Workshop, WG 2011, Teplá Monastery, Czech Republic, June 21-24, 2011. Revised Papers)
RedacteurenP. Kolman, J. Kratochvil
Plaats van productieBerlin
StatusGepubliceerd - 2011

Publicatie series

NaamLecture Notes in Computer Science
ISSN van geprinte versie0302-9743


Duik in de onderzoeksthema's van 'The Cinderella game on holes and anti-holes'. Samen vormen ze een unieke vingerafdruk.

Citeer dit