VoronoiGame on Graphs

location problem, where each market player comes up with a set of pos-
sible locations for placing their facilities. The objective of each player is
to maximize the region occupied on the underlying space. In this paper
we consider one round Voronoi game with two players. Here the under-
lying space is a road network, which is modeled by a graph embedded on
R2. In this game each of the players places a set of facilities and the un-
derlying graph is subdivided according to the nearest neighbor rule. The
player which dominates the maximum region of the graph wins. Given
a placement of facilities by Player 1, we have characterized the optimal
placement by Player 2. At first we dealt with the case when Player 2
places a constant number of facilities and provided an algorithm for the
same. Next we have proved that finding the optimal placement of k fa-
cilities by Player 2 is NP-hard where k is given. Lastly we presented a
1.58 factor approximation algorithm for the above mentioned problem..