Publication at Faculty of Mathematics and Physics |
2010
Abstract
We study a combinatorial game played by two players, Alice and Bob, on a given weighted graph G. The game generalizes the Pizza game considered by Brown, Winkler and others.
We show that, for every epsilon > 0 and for every k >= 1 there is a k-connected graph G for which Bob has a strategy to obtain 1-epsilon of the total weight of the vertices. We also study the computational complexity of deciding whether Alice has a winning strategy in this and one related game.