Geodesic
Advantage in the discrete Voronoi game
Journal of Graph Algorithms and Applications, Tome 18 (2014) no. 3, pp. 439-457.

Voir la notice de l'article provenant de la source Journal of Graph Algorythms and Applications website

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. 
@article{JGAA_2014_18_3_a7,
     author = {D\'aniel Gerbner and Viola M\'esz\'aros and D\"om\"ot\"or P\'alv\"olgyi and Alexey Pokrovskiy and G\"unter Rote},
     title = {Advantage in the discrete {Voronoi} game},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {439--457},
     publisher = {mathdoc},
     volume = {18},
     number = {3},
     year = {2014},
     doi = {10.7155/jgaa.00331},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00331/}
}
TY  - JOUR
AU  - Dániel Gerbner
AU  - Viola Mészáros
AU  - Dömötör Pálvölgyi
AU  - Alexey Pokrovskiy
AU  - Günter Rote
TI  - Advantage in the discrete Voronoi game
JO  - Journal of Graph Algorithms and Applications
PY  - 2014
SP  - 439
EP  - 457
VL  - 18
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00331/
DO  - 10.7155/jgaa.00331
LA  - en
ID  - JGAA_2014_18_3_a7
ER  - 
%0 Journal Article
%A Dániel Gerbner
%A Viola Mészáros
%A Dömötör Pálvölgyi
%A Alexey Pokrovskiy
%A Günter Rote
%T Advantage in the discrete Voronoi game
%J Journal of Graph Algorithms and Applications
%D 2014
%P 439-457
%V 18
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00331/
%R 10.7155/jgaa.00331
%G en
%F JGAA_2014_18_3_a7
Dániel Gerbner; Viola Mészáros; Dömötör Pálvölgyi; Alexey Pokrovskiy; Günter Rote. Advantage in the discrete Voronoi game. Journal of Graph Algorithms and Applications, Tome 18 (2014) no. 3, pp. 439-457. doi : 10.7155/jgaa.00331. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00331/

Cité par Sources :