Gerbner, D;
Mészáros, V;
Pálvölgyi, D;
Pokrovskiy, A;
Rote, G;
(2014)
Advantage in the discrete Voronoi game.
Journal of Graph Algorithms and Applications
, 18
(3)
pp. 439-457.
10.7155/jgaa.00331.
Preview |
Text
Pokrovskiy_Gerbner+2014.18.3.pdf - Published Version Download (489kB) | Preview |
Abstract
We study the discrete Voronoi game, where two players alternately claim vertices of a graph for t rounds. In the end, the remaining vertices are divided such that each player receives the vertices that are closer to his or her claimed vertices. We prove that there are graphs for which the second player gets almost all vertices in this game, but this is not possible for bounded-degree graphs. For trees, the first player can get at least one quarter of the vertices, and we give examples where she can get only little more than one third of them. We make some general observations, relating the result with many rounds to the result for the one-round game on the same graph.
| Type: | Article |
|---|---|
| Title: | Advantage in the discrete Voronoi game |
| Open access status: | An open access version is available from UCL Discovery |
| DOI: | 10.7155/jgaa.00331 |
| Publisher version: | https://doi.org/10.7155/jgaa.00331 |
| Language: | English |
| Additional information: | This is an Open Access article published under a Creative Commons Attribution 4.0 International (CC BY 4.0) Licence (https://creativecommons.org/licenses/by/4.0/). |
| UCL classification: | UCL UCL > Provost and Vice Provost Offices UCL > Provost and Vice Provost Offices > UCL BEAMS UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Maths and Physical Sciences UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Maths and Physical Sciences > Dept of Mathematics |
| URI: | https://discovery-pp.ucl.ac.uk/id/eprint/10112665 |
Archive Staff Only
 |
View Item |
