Home | Issues | About JGAA | Instructions for Authors |
DOI: 10.7155/jgaa.00235
The Voronoi game on graphs and its complexity
Vol. 15, no. 4, pp. 485-501, 2011. Regular paper.
Abstract The Voronoi game is a two-person game which is a model for a competitive
facility location. The game is played on a continuous domain, and only two
special cases (one-dimensional case and one-round case) are well investigated.
We introduce the discrete Voronoi game in which the game arena is
given as a graph.
We first analyze the game when the arena is a large complete k-ary tree,
and give an optimal strategy.
When both players play optimally, the first player wins when k is odd,
and the game ends in a tie for even k.
Next we show that the discrete Voronoi game is intractable in general.
Even for the one-round case in which the strategy adopted by the first player consist of
a fixed single node,
deciding whether the second player can win is NP-complete.
We also show that deciding whether the second player can win is PSPACE-complete in general.
|
Submitted: May 2009.
Reviewed: October 2009.
Revised: July 2011.
Accepted: August 2011.
Final: August 2011.
Published: August 2011.
Communicated by
Henk Meijer
|
Journal Supporters
|