Journal of Graph Algorithms and Applications
http://jgaa.info ISSN: 1526-1719
DOI: 10.7155/jgaa.00235 The Voronoi game on graphs and its complexity Sachio Teramoto , Erik D. Demaine , and Ryuhei Uehara 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.
|
Accepted: August 2011. Published: August 2011. Final: August 2011. Revised: July 2011. Reviewed: October 2009. Submitted: May 2009. Communicated by Henk Meijer |
Journal of Graph Algorithms and Applications |